Operating System

当所需页面不在内存中时，分为三种情况，当前内存中的页面数小于内存最大页面数时，添加一个新的页面为即当前所需页面，如果内存已满，则找出内存中的页面哪个页面下一次出现的最晚，或者是哪个页面不在出现，将它置换出来即可

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<string>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
using namespace std;
#define ll long long
const int N = 5e4 + 15;
int a[N];

int main()
{
    int n, m, q;
    while(cin >> n >> m >> q){
        queue<int>qu[N];
        set<int>st;
        set<int>s;
        for(int i = 0; i < q; i++)
            cin >> a[i], qu[a[i]].push(i), s.insert(a[i]);
        if(n >= m){
            cout << s.size() << endl;
            continue;
        }
        int res = 0;
        for(int i = 0; i < q; i++){
            //内存中已有此页面，从等待队列中剔除
            if(st.count(a[i]) != 0)
                qu[a[i]].pop();
            //内存未满，添加新页面
            else if(st.size() < n){
                st.insert(a[i]);
                qu[a[i]].pop();
                res += 1;
            }
            else{
                int p = 0, pos = -1;
                for(auto x : st){
                    //这个页面不在需要，置换出去
                    if(qu[x].empty()){
                        p = x;
                        break;
                    }
                    //这个页面下次出现次数将最晚，置换
                    if(qu[x].front() > pos){
                        pos = qu[x].front();
                        p = x;
                    }
                }
                st.erase(p);
                st.insert(a[i]);
                qu[a[i]].pop();
                res += 1;
            }
        }
        cout << res << endl;

    }
    return 0;
}