题解 | #[JSOI2010]缓存交换#

考察知识点：贪心、优先队列

模拟操作系统 MIN/OPT 换页机制，每次换页优先选择未来不会再访问的页或者在最长一段时间不会再访问的页（即当前缓存页中下次最晚访问的页），具体实现请见代码。

理论上，MIN/OPT 换页机制 是最优的内存换页机制，但是由于需要预知未来的访问情况，所以在实际应用中无法使用，只能作为一种理论参考。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n, m;
    cin >> n >> m;
    vi id(n + 1);
    for (int i = 0; i < n; i++)
        cin >> id[i];
    map<int, int> mp; // 记录每个id最后出现的位置
    vi next(n + 1);   // 下一次出现的位置
    for (int i = n; i >= 0; i--)
    {
        if (mp[id[i]] == 0)
            next[i] = n;
        else
            next[i] = mp[id[i]];
        mp[id[i]] = i;
    }
    vector<bool> cache(n + 1, false); // 是否在缓存中
    priority_queue<int> pq;           // 大根堆
    int ans = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (cache[i])
        {
            cache[next[i]] = true;
            pq.push(next[i]);
        }
        else
        {
            if (cnt == m)
            {
                cache[pq.top()] = false;
                pq.pop();
            }
            else
                cnt++;
            cache[next[i]] = true;
            pq.push(next[i]);
            ans++;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}