P3419 [POI2005]SAM-Toy Cars

链接：Miku、多组数据（蓝题和紫题的区别就是多组数据）

--------------------------------

非常显然的贪心思路就是能放就放，放满了然后把下一次使用间隔最久的拿走、

但是这样会有一个问题，如果它已经进去了怎么办，

直接continue会wa掉，因为即使已经有了，我们还是应该更新一下下一个的值（易证）

那么该怎么办呢

        if(pl[p[i]]){            x.id=p[i];            x.nex=nex[i];            q.push(x);            k  ;            continue;        }

这样扩大了地板，然后把原来的放到了一个永远不会被访问的部分，这样就对了

---------------------------------------

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;int n,k;struct to{    int id;    int nex;    friend bool operator < (to a,to b){        return a.nex<b.nex;//我一直很奇怪为什么这是反的     }} x;priority_queue <to>q;int nex[500101],last[500101];int p[500011];int pp;int cnt;int pl[500101];int main(){    scanf("%d%d%d",&n,&k,&pp);    for(int i=1;i<=pp;  i){        scanf("%d",&p[i]);        nex[last[p[i]]]=i;        last[p[i]]=i;    }//寻找下一个     for(int i=1;i<=n;  i){        nex[last[i]]=0x3f3f3f;    }//处理下最后的部分     for(int i=1;i<=pp;  i){        if(pl[p[i]]){            x.id=p[i];            x.nex=nex[i];            q.push(x);            k  ;            continue;        }        if(q.size()<k){//能放就放，除非已有             x.nex=nex[i];            x.id=p[i];        q.push(x);        cnt  ;        pl[p[i]]=1;        }else{//先拿再放             x=q.top();            q.pop();            pl[x.id]=0;            x.nex=nex[i];            x.id=p[i];            q.push(x);            cnt  ;            pl[x.id]=1;        }    }    cout<<cnt;    return 0;}

多组数据版

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#include<cstring>using namespace std;int n,k;int h;struct to{    int id;    int nex;    friend bool operator < (to a,to b){        return a.nex<b.nex;    }} x;priority_queue <to>q;int nex[500101],last[500101];int p[500011];int pp;int cnt;int pl[500101];int main(){    scanf("%d",&h);    for(int j=1;j<=h;  j){        memset(p,0,sizeof(p));        memset(nex,0,sizeof(nex));        memset(last,0,sizeof(last));        memset(pl,0,sizeof(pl));        cnt=0;        while(!q.empty())        q.pop();    scanf("%d%d%d",&n,&k,&pp);    for(int i=1;i<=pp;  i){        scanf("%d",&p[i]);        nex[last[p[i]]]=i;        last[p[i]]=i;    }    for(int i=1;i<=n;  i){        nex[last[i]]=0x3f3f3f;    }    for(int i=1;i<=pp;  i){        if(pl[p[i]]){            x.id=p[i];            x.nex=nex[i];            q.push(x);            k  ;            continue;        }        if(q.size()<k){            x.nex=nex[i];            x.id=p[i];        q.push(x);        cnt  ;        pl[p[i]]=1;        }else{            x=q.top();            q.pop();            pl[x.id]=0;            x.nex=nex[i];            x.id=p[i];            q.push(x);            cnt  ;            pl[x.id]=1;        }    }    cout<<cnt<<endl;    }    return 0;}

 

来源：https://www.icode9.com/content-4-722201.html