题解 | #[JSOI2010]缓存交换#

1. 本题的贪心该怎么想，为什么要窗口中距离最远的数，如果一个元素很快被访问，我们保留它，可以减少Miss的次数，如果一个元素很后面被访问，如果我们保留它，他将会占据格子，换出他的影响最小。这个就是为什么贪心。
2. 我们用vis数组来记录他是否再窗口中，因为我们要与窗口相同但是距离最远的数，所以我们要存一个数出现下一个位置的下标，用unordered_map来存辅助初始化next0数组。

using namespace std;
const int N = 1e5+20;
int vis[N];
int next0[N];
int arr[N];
#define int long long
void solved(){
    int n,m;
    cin>>n>>m;
    unordered_map<int,int>mp;
    priority_queue<int>pq;
    for(int i = 1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i = n;i>=1;i--){
        if(mp[arr[i]]==0) next0[i] = N;
        else next0[i] = mp[arr[i]];
        mp[arr[i]] = i;
    }
    int ans = 0;
    int num = 0;
    for(int i = 1;i<=n;i++){
        if(vis[i] == 0){//就是代表这个数不在窗口中
            ans++;
            if(num<m){
                num++;
                vis[next0[i]]=1;
                pq.push(next0[i]);
            }else{
               vis[pq.top()] = 0;
                pq.pop();
                vis[next0[i]] = 1;
                pq.push(next0[i]);
            }
        }else{
            vis[next0[i]]= 1;
            pq.push(next0[i]);
        }
    }
    cout<<ans<<endl;
}

signed main(){
    solved();
    return 0;
}