前言:这道题目的前面的几个题解写的真的不错,我感觉这道题挺难理解的,需要沉下心思来思考

大的前提:缓存中每个数字的大小范围是1e9级别,不可能用容器直接存下.所以用于标记和比较的容器里存的是第i个数的下标

调度策略:只出现一次的数据,优先级最低,应该最先把这种数据从缓存中移除.其他的数据,出现的越晚优先程度越低.对于时刻更新的缓存,优先程度也是时刻更新的,所以用优先队列来实现

PS:这道题题目对于缓存调度策略的描述不够严谨,要是知道能存下来(知道)接下来要存的数,那就不需要缓存 所以这种调度策略是不可能实现的

AC代码&思路:

#pragma GCC optimize("Ofast,no-stack-protector")
#include<iostream>
#include<queue>
#include<bitset>//此处当作bool数组
#include<map>//此处用来延迟存放数据
#define maxn 100000
using namespace std;
bitset<maxn+10> note;
int nexti[maxn+10];
int datai[maxn+10];
map<int, int> mp;
priority_queue<int> priqu;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int m,n,cnt=0,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;++i) {cin>>datai[i];}
    for(int i=n;i>=1;--i) //注意要倒着检索
    {
        if(mp[datai[i]] == 0) {nexti[i]=maxn+7;}//在这之前从没出现过(第一次出现)这个数,就设定下一个出现的位置为一个不可能达到的位置(优先队列中永远排队首),反正如果之前再出现,还可以改
        else {nexti[i]=mp[datai[i]];}//如果在前面又碰到这个数了:记录下一次这个数出现的位置
        mp[datai[i]]=i;//更新当前i对应的值的最新(最前)出现位置为当前位置i
        //为什么要错位更新?因为是找下一次出现的位置,所以用倒着找,mp记录延迟一次更新的位置,nexti[]中的某个位置记录的是延迟一次的位置,那么就是最近下一次出现的位置了
        //为什么要用map?因为map键值对的特性,一个键只能对应一个值,当i往前找遇到同样的data[i]时,最新最前的位置i就可以覆盖掉后面的i
    }
    for(int i=1;i<=n;++i)
    {
        if(note[i]==0)//缓存中没有这个数
        {
            ++ans;//记录未命中次数
            if(cnt==m) //缓存满了,因为每次输入数据都更新,所以不用>=
            {
                note[priqu.top()]=0;
                priqu.pop();//清空缓存中在数组中最后一个出现的某个元素
            }
            else {++cnt;}//缓存还有
        }
      //如果缓存未命中,无论如何,总会把当前数存入缓存(依据贪心策略)
      //如果缓存命中了,那么也要把当前数更新下一个当前数(类似链表?因为nexti存的是第i个数下一次出现的位置,而不是下一次及下下一次及下下下...出现的位置)
        note[nexti[i]]=1;
        priqu.push(nexti[i]);
    }
    cout<<ans;
    return 0;
}