經典貪心

策略如下：

每次貪心讓最需要的放下

易證正確

#include<bits/stdc++.h> using namespace std; const int N=1e6; inline void read(int &x){x=0;char ch=getchar();int f=1;while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f; } int val[N]={}; int nxt[N]={}; int last[N]={}; int n,k,p; int siz=0; int ans=0; priority_queue<pair<int,int> > Q; int inqueue[N]={}; int main(){read(n);read(k);read(p);for(int i=1;i<=p;i++){read(val[i]);}for(int i=1;i<=p;i++){nxt[last[val[i]]]=i;last[val[i]]=i;}for(int i=1;i<=n;i++)nxt[last[i]]=1e9+7;for(int i=1;i<=p;i++){if(inqueue[val[i]]){pair<int,int> tmp;tmp.first=nxt[i];tmp.second=val[i];Q.push(tmp); }else{siz++;ans++;if(siz>k){siz--;inqueue[Q.top().second]=0;Q.pop();}inqueue[val[i]]=1;pair<int,int> tmp;tmp.first=nxt[i];tmp.second=val[i];Q.push(tmp);}}cout<<ans; }

轉載于:https://www.cnblogs.com/Leo-JAM/p/10079220.html

總結

以上是生活随笔為你收集整理的省选专练[POI2005]SAM-Toy Cars的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。