Luogu P4404 [JSOI2010]缓存交换 优先队列

时间:2022-07-12 11:36:12

细节题?、、、调了半天。。。。


可以发现,每一次从缓存中删除的主存一定是下次访问最晚的,可以用优先队列来处理。。。还有要离散化。。。还有链表末尾要多建一些点、、、否则会死的很惨、、、

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#define R register int
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,sz,vis,tot,cnt,ans;
int a[],lst[],nxt[];
bool v[];
priority_queue<int>q;
map<int,int>mp;
signed main() {
n=g(),sz=g();
for(R i=,x;i<=n;++i) {
x=g(); if(mp.find(x)==mp.end()) a[i]=mp[x]=++tot; else a[i]=mp[x];
nxt[lst[a[i]]]=i,lst[a[i]]=i;
} for(R i=;i<=tot;++i) nxt[lst[i]]=n+i,a[n+i]=i;
for(R i=;i<=n;++i) { while(q.size()&&!v[a[q.top()]]) q.pop();
if(v[a[i]]) {q.push(nxt[i]); continue;}
if(cnt<sz) {v[a[i]]=true,q.push(nxt[i]),++ans,++cnt; continue;}
v[a[q.top()]]=false,q.pop(),v[a[i]]=true,q.push(nxt[i]),++ans;
} printf("%d\n",ans);
}

2019.04.24