题解 | #OperatingSystem#

思路

下一次出现最晚的 被 弹出队列 ==> 最佳页面置换算法 （OPT）
而不是 剩余出现次数最少的 被 弹出队列

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;

struct node{
    int id;
    int nex;
    bool operator < (const node &x) const { return nex < x.nex ;}
};
bool st[N];
int pos[N],Nex[N];
int a[N];
int n,m,q;
int res;

void Init(){
    memset(pos,0x3f,sizeof pos);
    memset(st,false,sizeof st);
}

int main(){
    while(cin>>n>>m>>q){
        Init();  priority_queue<node> heap;
        int k=0;
        for(int i=1;i<=q;i++) cin>>a[i];
        for(int i=q;i>=1;i--){
            Nex[i]=pos[a[i]];
            pos[a[i]]=i;
        }

        for(int i=1;i<=q;i++){
            int id=a[i];

            if(k<n&&!st[id]){
                res++;
                st[id]=true;
                k++;    
            }
            else if(k==n&&!st[id]){
                res++;
                auto t=heap.top();
                heap.pop();
                st[t.id]=false;
                st[id]=true;
            }
            heap.push({id,Nex[i]});
        }  
        cout<<res<<endl;   res=0;
    }

    return 0;
}