首先考虑一个贪心策略：当地板已经放满需要取出一个时，取下一次使用时间 \(nxt\) 最晚的那个。
所以我们只需要一个可以快速求出一个集合中 \(nxt\) 最小的点并删除，插入新点的数据结构，这里很容易想到堆。
代码很简洁，注意数组的下标是位置还是颜色（考场 100 pts 到 0 pts）。
code:
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define debug cout<<"debug\n"
#define vi vector<int>
#define imp map<int,int>
#define il inline
#define pb push_back
using namespace std;
const int N=5e5+5,M=1e5+5;
int n,k,p,a[N],nxt[N];
bool vis[N];
vi g[M];
struct cmp{
bool operator ()(const int &x,const int &y){
return nxt[x]<nxt[y];
}
};
priority_queue<int,vi,cmp>pq;
int ans=0;
int main(){
cin>>n>>k>>p;
for(int i=1;i<=p;i++){
cin>>a[i];
g[a[i]].pb(i);
}
for(int i=1;i<=n;i++){
if(g[i].size()==0) continue;
for(int j=0;j<g[i].size()-1;j++){
nxt[g[i][j]]=g[i][j+1];
}
nxt[g[i][g[i].size()-1]]=p+1;
}
/*for(int i=1;i<=p;i++){
cout<<nxt[i]<<" ";
}
cout<<"\n";*/
for(int i=1;i<=p;i++){
int x=a[i];
if(!vis[x]){
if(pq.size()==k){
vis[a[pq.top()]]=0;
pq.pop();
}
vis[x]=1;
ans++;
pq.push(i);
}else{
k++;
pq.push(i);
}
}
cout<<ans<<"\n";
return 0;
}