题解 | #OperatingSystem#

大概题意：

N的内存，M的页面，N刚开始为空，M页面表示页面编号从1->M,Q次询问 问需要添加或置换的次数最小是多少。 贪心

思路：

需要一个数据结构存储页面，简写为q有新的元素准备进入的时候，分为三种情况，第一种q情况没满。第二种情况，q满了，看已经在队列里面的数，谁的相同的下一个数离的最远就替换掉谁。第三种情况，q满了，但是新的元素的同值存在。 离得远，i对应的大，根据离得远近，来排列队列里的数，会想到优先队列，大根堆，不是按照数值排序，需要pair<int,int>。 为了判断是第二种还是第三种情况，需要一个bool数组判断是否元素已经存在在堆里。

重点部分：（贪心的维护）

需要维护，每个位置，对应的值，下次出现在哪个位置。

假设是值仅出现一次，那默认为无穷远。（0x3f）now初始化为无穷远。另外一个随便。0或者无穷远。0取不到的。

意思是希望下标就可以引出值对应的下一个位置。i->位置[a[i]]。

位置[a[i]]->下个位置。 数组的下标对应数组的值。

ntx[]下标是位置，值是位置对应的a值的下一个a值的位置。

所以还需要一个now【】下标是a值，值是a值此时的位置。

ntx：从位置对应到值的下一个位置。now从值对应到此时的位置。

都说了是下一个位置，肯定是从大到小遍历。

源代码：

using namespace std;
const int N=5e4+10;
priority_queue<pair<int,int>> qu;//需要把某个元素，和它的下个位置绑定在一起。
int nxt[N],now[N],a[N];
bool st[N];
int n,m,q;
int ans;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n>>m>>q){
        ans = 0;
        memset(nxt,0,sizeof nxt);
        memset(now,0x3f,sizeof now);
        memset(st,0,sizeof st);        
        while(qu.size()) qu.pop();//新的开始必须要先重制
        for(int i=1;i<=q;i++) cin>>a[i];
        for(int i=q;i>0;i--){
            nxt[i] = now[a[i]];
            now[a[i]] = i;
        }
        int tmp = 0;//记录重复的数
        for(int i=1;i<=q;i++){
            if(st[a[i]]) tmp++;//假如数重复了
            if(!st[a[i]] && qu.size()<n+tmp){
                ans++;
                st[a[i]] = 1;
            }
            else if(qu.size()==n+tmp && !st[a[i]]) {
                ans++;
                st[qu.top().second] = 0;
                qu.pop();
                st[a[i]] = 1;
            }
            qu.push({nxt[i],a[i]});//希望达到的效果是，按照nxt的大小排序,就算a值相同，再次读入也是大的更有可能为顶。放在循环语句外面，意思是三种情况都要推进元素。
        }
        cout<<ans<<"\n";
    }
}