BZOJ 1528 [POI2005]sam-Toy Cars（优先队列）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1528

【题目大意】

　　地上最多可以放k个玩具，现在给出需求顺序，
　　问最少需要去架子上拿几次玩具

【题解】

　　用优先队列维护地上玩具距离下次被需求时间节点大小，
　　每次出列时间距离最远玩具放回架子，然后从架子上拿下当前的需求

【代码】

#include <cstdio>

#include <algorithm>

#include <queue>

using namespace std;

typedef pair<int,int> P;

priority_queue<P,vector<P> >Q;

const int N=500010;

int n,m,k,ans,a[N],nxt[N],lst[N];

bool inq[N];

int main(){

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

    for(int i=1;i<=n;i++)lst[i]=m+1;

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

    for(int i=m;i;i--)nxt[i]=lst[a[i]],lst[a[i]]=i;

    for(int i=1;i<=m;i++){

        if(inq[a[i]]){Q.push(make_pair(nxt[i],a[i]));continue;}

        if(k){ans++;Q.push(make_pair(nxt[i],a[i]));inq[a[i]]=1;k--;}

        else{

            while(!inq[Q.top().second])Q.pop();

            inq[Q.top().second]=0; Q.pop();

            ans++; Q.push(make_pair(nxt[i],a[i]));

            inq[a[i]]=1;

        }

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

    return 0;

}