题解 | #OperatingSystem#

OperatingSystem

https://ac.nowcoder.com/acm/problem/15688

思路

下一次出现最晚的 被 弹出队列 ==> 最佳页面置换算法 (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;
}
全部评论

相关推荐

07-14 12:22
门头沟学院 Java
点赞 评论 收藏
分享
07-14 12:29
门头沟学院 Java
后端岗,实习三周感觉有点想跑路了,担心秋招被拉黑,有没有佬是字节HR知道情况的
从零开始的转码生活:你实习三周都想跑路,将来拿到offer真的愿意在这干十几二十年吗
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务