【BZOJ1826】[JSOI2010]缓存交换(贪心)

【BZOJ1826】[JSOI2010]缓存交换(贪心)

题面

BZOJ

洛谷

题解

当缓存不满显然直接放进去,满了之后考虑拿走哪一个。不难发现拿走下一次出现时间最晚的那个一定不会更差。

那么用一个堆维护这个东西即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,top,ans,S[MAX],a[MAX];
int nxt[MAX],lst[MAX];
struct Node{int p;};
bool operator<(Node a,Node b){return nxt[a.p]<nxt[b.p];}
int vis[MAX];int tot;
struct Heap
{
priority_queue<Node> Q1,Q2;
void push(int a){Q1.push((Node){a});}
void del(int a){Q2.push((Node){a});}
Node top()
{
while(!Q2.empty()&&Q1.top().p==Q2.top().p)
Q1.pop(),Q2.pop();
return Q1.top();
}
}Q;
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)S[++top]=a[i]=read();
sort(&S[1],&S[n+1]);top=unique(&S[1],&S[n+1])-S-1;
for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[top+1],a[i])-S;
memset(lst,63,sizeof(lst));
for(int i=n;i>=1;--i)nxt[i]=lst[a[i]],lst[a[i]]=i;
for(int i=1;i<=n;++i)
{
if(vis[a[i]])
{
Q.del(vis[a[i]]);
vis[a[i]]=i;
Q.push(vis[a[i]]);
continue;
}
if(tot<m)Q.push(i),vis[a[i]]=i,++tot,++ans;
else
{
int u=Q.top().p;Q.del(u);
vis[a[u]]=0;--tot;
Q.push(i);vis[a[i]]=i;
++ans;++tot;
}
}
printf("%d\n",ans);
return 0;
}
上一篇:linux工具类之流量监视


下一篇:BZOJ_3307_雨天的尾巴_线段树合并+树上差分