[POI2005]Toy Cars

题目大意：
　　有n种物品，地上有k个格子，p次操作。
　　每次操作要求将某一个指定的物品移动到任意一个格子中，同时你可以选择是否将格子中的某一个物品收起来，并消耗1的代价。
　　如果下达指令时，这个物品刚好在格子上，那么就不会消耗代价。
　　问至少消耗多少代价？

思路：
　　贪心。
　　每次移动如果时，如果地板上已经放慢了物品，那么就应该把第二次出现最晚的物品收起来。
　　预处理每一次指令对应的物品第二次出现的时刻。
　　用一个堆来维护当前地板上的物品即可。

 #include<cstdio>

 #include<cctype>

 #include<hash_set>

 #include<ext/pb_ds/priority_queue.hpp>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,P=;

 int a[P],cnt[N],pos[N],next[P];

 __gnu_cxx::hash_set<int> set;

 __gnu_pbds::priority_queue<std::pair<int,int> > q;

 __gnu_pbds::priority_queue<std::pair<int,int> >::point_iterator p[N];

 int main() {

     const unsigned n=getint(),k=getint(),p=getint();

     for(register unsigned i=;i<=p;i++) {

         a[i]=getint();

         cnt[a[i]]++;

     }

     for(register unsigned i=;i<=n;i++) pos[i]=p+;

     for(register unsigned i=p;i;i--) {

         next[i]=pos[a[i]];

         pos[a[i]]=i;

     }

     unsigned ans=,i=;

     for(;set.size()<k&&set.size()<n&&i<=p;i++) {

         if(!set.count(a[i])) {

             ans++;

             set.insert(a[i]);

             ::p[a[i]]=q.push(std::make_pair(next[i],a[i]));

         } else {

             q.modify(::p[a[i]],std::make_pair(next[i],a[i]));

         }

     }

     for(;i<=p;i++) {

         if(!set.count(a[i])) {

             ans++;

             set.erase(q.top().second);

             q.pop();

             set.insert(a[i]);

             ::p[a[i]]=q.push(std::make_pair(next[i],a[i]));

         } else {

             q.modify(::p[a[i]],std::make_pair(next[i],a[i]));

         }

     }

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

     return ;

 }