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

链接：https://ac.nowcoder.com/acm/contest/22904/1006
来源：牛客网

题目描述

本题贪心的策略就是，每次替换掉离目前位置最远的单元。

为什么不能是最近呢？因为替换掉离目前位置最近的单元，部分情况下会导致频繁替换

举个例子

设Cache的空间大小为2

1 2 3 1 4 1 5 1 2 2 2

可以看出，如果运行到3，4，5时，将距离最近的1换成3，4，5，那么很明显最后的总次数会增加很多，而如果将距离最远的2换成3，4，5，那么1会一直保留，这样总次数会大大减少

代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int tmp[100020],nextp[100020],usd[100020]; //nextp数组存储每个相同元素的下一个位置，usd数组存储目前可以直接访问而不增加ans次数的内存单元位置 
priority_queue<int,vector<int>>da; //存储相同内存单元的下一个位置 
map<int,int>mp; //map映射内存单元与位置下标的关系
int main(){
    int n,m,ans=0,num=0; //ans存储缺失次数，num存储Cache中的内存单元个数 
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&tmp[i]);
    for(int i=n;i>=1;i--){//构造相同元素的下一个位置的数组 
        if(mp[tmp[i]]==0) nextp[i]=100020; //表示此元素为最后一个元素 
        else nextp[i]=mp[tmp[i]];
        mp[tmp[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(usd[i]==0){ //未存储在内存中，增加ans 
            ans++;    
            if(num<m){ //内存没有满，直接加入内存即可 
                num++;
                da.push(nextp[i]);
                usd[nextp[i]]=1;
            }else{ //内存满了（贪心），将离目前的位置最远的单元替换为此单元。 
                usd[da.top()]=0; //更新usd状态，表示此单元已经不在Cache中 
                da.pop();
                da.push(nextp[i]);
                usd[nextp[i]]=1;
            }
        }else{ //已经存储在内存中了，不增加ans，只需要把队列里的值更新一下就行 
            usd[nextp[i]]=1;
            da.push(nextp[i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}