【优先队列+贪心】BZOJ1826-[JSOI2010]缓存交换

……啊开始颓了。

【题目大意】

已知当前集合最大容量为m，n个询问。每次询问一个元素，如果集合中没有则需要加入该元素，如果集合已经满了则需要先删去集合中的某些元素再加入。问至少要加入几次元素？

【思路】

显然每一次删除的元素是下一次出现最晚的那一个，优先队列维护一下就好了。

【错误点】

非常ZZ地把集合满的条件定为了“que.size()==m”，实际上如果该元素已经存在，我们更新下一次出现的时候原来的在优先队列中是不删除的。所以必须另外设一个qsize记录集合中有几个元素存在。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=;

 typedef pair<int,int> p;

 const int INF=0x7fffffff;

 int n,m,a[MAXN],d,hash[MAXN];

 int rcap[MAXN],nap[MAXN];//recently appear & next appear

 priority_queue<p> que;

 int inque[MAXN],qsize;

 void init()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=n;i++) scanf("%d",&a[i]),hash[i]=a[i];

     sort(hash+,hash+n+);

     d=unique(hash+,hash+n+)-(hash+);

     for (int i=;i<=n;i++) a[i]=lower_bound(hash+,hash+d+,a[i])-hash;

     for (int i=;i<=n;i++) rcap[i]=nap[i]=INF;

     for (int i=;i<=n;i++)

     {

         if (rcap[a[i]]!=INF) nap[rcap[a[i]]]=i;

         rcap[a[i]]=i;

     }

 }

 void solve()

 {

     int ans=;

     memset(inque,,sizeof(inque));

     qsize=;

     for (int i=;i<=n;i++)

     {

         if (!inque[a[i]])

         {

             if (qsize==m) //这里不能用que.size()代替，因为相同元素可能都在优先队列里呢

             {

                 inque[que.top().second]=;

                 que.pop();

                 qsize--;

             }

             inque[a[i]]=;

             ans++;

             qsize++;

         }

         que.push(p(nap[i],a[i]));

     }

     printf("%d\n",ans);

 }

 int main()

 {

     init();

     solve();

     return ;

 }