当所需页面不在内存中时,分为三种情况,当前内存中的页面数小于内存最大页面数时,添加一个新的页面为即当前所需页面,如果内存已满,则找出内存中的页面哪个页面下一次出现的最晚,或者是哪个页面不在出现,将它置换出来即可
#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; }