[bzoj1826] [JSOI2010]缓存交换

时间:2022-08-02 11:35:37

  虽然不知道为什么。。但显然,每次扔掉离下次查询最远的内存单元就行了233

  用堆来维护贪心。。。(优先队列大法好

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#define d double
using namespace std;
const int maxn=;
const int inf=;
struct zs{
int v,pos;
}a[maxn];
struct zzs{
int next,v;
};
priority_queue<zzs>q;
int b[maxn],next[maxn];
int i,j,k,n,m,ans;
bool inq[maxn]; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
bool cmp(zs a,zs b){return a.v==b.v?a.pos<b.pos:a.v<b.v;} bool operator <(zzs a,zzs b){
return a.next<b.next;
}
int main(){
n=read(),m=read();
for(i=;i<=n;i++)a[i].v=read(),a[i].pos=i;
sort(a+,a++n,cmp);int last=,cnt=;
for(i=;i<=n;i++)if(a[i].v!=a[i+].v||i==n){
cnt++;
for(j=last;j<i;j++)
next[a[j].pos]=a[j+].pos;
next[a[i].pos]=inf;
for(j=last;j<=i;j++)b[a[j].pos]=cnt;
last=i+;
}
// for(i=1;i<=n;i++)printf(" %d",b[i]);puts("");
int sz=;zzs tmp;
for(i=;i<=n;i++){
if(sz==m&&!inq[b[i]]){
while(!q.empty()&&!inq[q.top().v])q.pop();
if(q.empty())continue;
tmp=q.top(),q.pop();
sz--;//printf("%d out:%d\n",i,tmp.v);
inq[tmp.v]=;
}
if(!inq[b[i]])sz++,inq[b[i]]=,ans++;
q.push((zzs){next[i],b[i]});
}
printf("%d\n",ans);
return ;
}