-------------------------------- 非常显然的贪心思路就是能放就放,放满了然后把下一次使用间隔最久的拿走、 但是这样会有一个问题,如果它已经进去了怎么办, 直接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./content-4-722201.html |
|