普通版：

#include <bits/stdc++.h>
using namespace std;
int n, m;
map<int,int> mp;//用于负责构造nexti[i]数组
bool boo[100050];//表示Cache中的内存。boo[2]=1表示a[2]在Cache中
int nexti[100050];//nexti[1]=3表示a[1]接下来最近的与a[1]相同的是a[3]
int ar[100050];
priority_queue<int> q;//储存最近的与Cache中的元素相同的元素的下标
                      //boo中有多少个元素等于1,则q中就至少有这些元素
int num, ans;//num表示Cache中已经有多少个元素，ans记录答案
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
    for(int i = n; i > 0; --i)//构造nexti[i]数组，表示下一个与a[i]相同的数的下标是几，不纯在则为N
    {
        if(mp[ar[i]] == 0)  nexti[i] = 100050;
        else    nexti[i] = mp[ar[i]];
        mp[ar[i]] = i;//用mp[a[i]]=i记录上一次a[i]的下标i,下一次遇到a[i]时next[i]=mp[a[i]]=该下标
    }
    
    for(int i = 1; i <= n; ++i)
    {
        if(boo[i] == 0)//a[i]若不在Cache中
        {
            ans++;//进行缺失操作，答案数++
            if(num < m)//Cache没有满
            {
                num++;//Cache中元素+1
                boo[nexti[i]]=1;//标记将该a[i]存入Cache，即下一次遇到a[i]时显示a[i]在Cache中
                                //等价于把下一次出现的a[i]的下标标记
                q.push(nexti[i]);//把下一次出现a[i]的位置的下标存入q
            }
            else//Cache满了
            {
                boo[q.top()] = 0;//删掉最晚要用再次到的，即q中储存的所有下标中下标最大的
                q.pop();
                boo[nexti[i]]=1;//存入当前要用的a[i]，等价于标记下一次出现a[i]的位置的下标
                q.push(nexti[i]);//把下一次出现a[i]的位置的下标存入q
            }
        }
        else//a[i]在Cache中，不需要进行缺失操作，但需要把更大的下标存入q并标记下一次a[i]任在Cache中
        {
            boo[nexti[i]] = 1;//a[i]还在Cache中，下一次遇到a[i]时任然显示a[i]在Cache中
                              //等价于再把下一次出现的a[i]的下标标记
            q.push(nexti[i]);//把下一次出现a[i]的位置的下标存入q
        }
    }
    printf("%d\n", ans);
    return 0;
}

遍历时无论a[i]是否在Cache中，下次遇到a[i]时，都要显示a[i]在Cache中 并且要将下一次a[i]出现的位置的下标存入q 所以这两行操作在遍历每个a[i]时都要进行，故可以写在if外面进行简化 简化版

#include <bits/stdc++.h>
using namespace std;
int n, m;
map<int,int> mp;
bool boo[100050];//表示Cache中的内存。boo[2]=1表示a[2]在Cache中
int nexti[100050];//nexti[1]=3表示a[1]接下来最近的与a[1]相同的是a[3]
int ar[100050];
priority_queue<int> q;//储存最近的与Cache中的元素相同的元素的下标
                      //boo中有多少个元素等于1,则q中就至少有这些元素甚至更多
int num, ans;//num表示Cache中已经有多少个元素，ans记录答案
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
    for(int i = n; i > 0; --i)//构造nexti[i]数组，表示下一个与a[i]相同的数的下标是几，不纯在则为N
    {
        if(mp[ar[i]] == 0)  nexti[i] = 100050;
        else    nexti[i] = mp[ar[i]];
        mp[ar[i]] = i;//用mp[a[i]]=i记录上一次a[i]的下标i,下一次遇到a[i]时next[i]=mp[a[i]]=该下标
    }
    
    for(int i = 1; i <= n; ++i)
    {
        if(boo[i] == 0)//a[i]若不在Cache中
        {
            ans++;//进行缺失操作，答案数++
            if(num < m) num++;//Cache没有满,Cache中元素+1  
            else//Cache满了
            {
                boo[q.top()] = 0;//删掉最晚要用再次到的，即q中储存的所有下标中下标最大的
                q.pop();   
            }
        }
        boo[nexti[i]] = 1;//标记将该a[i]存入Cache，即下一次遇到a[i]时显示a[i]在Cache中
                          //等价于把下一次出现的a[i]的下标标记
        q.push(nexti[i]);//把下一次出现a[i]的位置的下标存入q
    }
    printf("%d\n", ans);
    return 0;
}