题目链接

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

题意

容量为n的内存，有1-m编号的页面，有q个请求，每个请求包含一个页面，内存里面没有这个页面的话，就会记录一次缺页，并放入内存，内存满了就会置换其中一个页面，求缺页次数最少。

思路

如需置换，置换晚出现的页面。

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MINF = 0x3f3f3f;
const double eps = 1e-9;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int N = 50000;
int n, m, q;
int a[N + 5];
int vis[N + 5]; //a[i] 下一次出现的序号
bool bl[N + 5]; //页面是否有被访问
map<int, int> mp; //a[i] 出现的序号

void solve() {
    while (cin >> n >> m >> q) {
        mp.clear();
        ll cnt = 0;
        ll num = 0; // 内存里面页面有多少，注意不要用堆的size
        priority_queue<ll, vector<ll>, less<ll>> qu; //记录下一次出现晚的编号
        memset(bl, false, sizeof bl);
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= q; i++)
            scanf("%d", &a[i]);
        for (int i = q; i >= 1; i--) {
          	//如果之后没有再出现该内存的话，我们就将其vis置为q + 1(一定不会被访问的结点)
            if (mp.find(a[i]) == mp.end())
                vis[i] = q + 1;
            else
                vis[i] = mp[a[i]];
            mp[a[i]] = i;
        }
        for (int i = 1; i <= q; i++) {
          	//如果页面没有被访问
            if (!bl[i]) {
              	//记录缺页
                cnt++;
                if (num < n) {
                  	//内存未满
                    num++;
                } else {
                  	//内存已满，将下一次出现次数晚的先删掉
                    bl[qu.top()] = false;
                    qu.pop();
                }
            }
          	//更新该页面下一次出现的序号
            bl[vis[i]] = true;
            qu.push(vis[i]);
        }
        cout << cnt << '\n';
    }
}

int main() {
    int _ = 1;
//    scanf("%d", &_);
    while (_--) {
        solve();
    }
    return 0;
}