[JSOI2010 缓存交换]贪心、二叉堆

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1826
【算法分析】
如果一个x已经在缓存中，那么本次x进入就不需要再被计算。
也就是说，无论弄谁，本质上都是一样的。
而且当前这个点，必须被push进缓存。
容易得到一个贪心解法：
设当前值为x，就是按下一个x的位置前后排个序里，越后的越废。
于是只取前m个就可以了。于是可以用个二叉堆优化。
【时间复杂度】O(n lg n)
【其它】2Y。一开始把堆得del函数写错了呃@.@，因为删的不一定是第一个，写不习惯了。。
【CODE】
#include using namespace std;
const int N=105555;
struct edge{int y,next,pos;}g[N];
int n,m,e;
int a[N],lx[N],ls[N],Next[N],zz[N];

struct Heap_t{
int tot;
struct Node{int key,pos;}h[N];
void Swap(int i,int j){
Node tmp=h[i]; h[i]=h[j]; h[j]=tmp;
zz[h[i].pos]=i;
zz[h[j].pos]=j;
}
void up(int k){
while (k>1 && h[k].key>h[k/2].key){
Swap(k,k/2);
k/=2;
}
}

void down(int p){
int k;
while (p*2<=tot){
k=p*2;
if (k if (h[k].key>h[p].key){
Swap(k,p);
p=k;
}else break;
}
}

void ins(int key,int pos){
tot++;
h[tot].key=key;
h[tot].pos=pos;
zz[pos]=tot;
up(tot);
}

void del(int p){
Swap(p,tot);
zz[h[tot].pos]=0;
tot–;
up(p);
down(p);
}
}heap;

int Find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>lx[mid]) l=mid+1;
else r=mid;
}
return l;
}

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
lx[i]=a[i];
}
sort(lx+1,lx+n+1);
for (int i=1;i<=n;i++) a[i]=Find(a[i]);
for (int i=1;i<=n;i++) ls[i]=n+1;
for (int i=n;i>=1;i–){
Next[i]=ls[a[i]];
ls[a[i]]=i;
}
}

void work(){
memset(zz,0,sizeof(zz));
heap.tot=0;
int i,ans=0;
for (i=1;i<=n;i++){
if (zz[a[i]]==0){
ans++;
if (heap.tot==m) heap.del(1);
heap.ins(Next[i],a[i]);
}
else{
heap.del(zz[a[i]]);
heap.ins(Next[i],a[i]);
}
}
printf("%dn",ans);
}

int main(){
init();
work();
}