经典贪心：

• 若不满，则直接放。
• 若满，则弹出当前 Cache 中距离下一次出现位置最远的元素。

对于当前 Cache 中所有元素，显然选取上述最优。

使用堆来维护即可：

// Problem: [JSOI2010]缓存交换
// Made by: Acc_Robin
#include<iostream>
#include<queue>
using namespace std;
int main(){
 int n,m,c=0,i,z=0;
 cin>>n>>m;
 vector<int>a(n),b(n),f(n);
 for(int&i:a)cin>>i;
 b=a,sort(begin(b),end(b));
 b.erase(unique(begin(b),end(b)),end(b));
 for(int&i:a)i=lower_bound(begin(b),end(b),i)-begin(b);
 vector<int>g(b.size(),1e9),vs(b.size());
 for(i=n-1;~i;--i)f[i]=g[a[i]],g[a[i]]=i;
 priority_queue<pair<int,int>>q;
 for(i=0;i<n;++i)if(!vs[a[i]]){
  if(++z,c<m)++c;
  else vs[a[q.top().second]]=0,q.pop();
  vs[a[i]]=1,q.emplace(f[i],i);
 }else q.emplace(f[i],i);
 cout<<z<<'\n';
}