【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;

}