题解 | 机器翻译

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m, n, cache = 0, time = 0;//cache记录当前缓存内用了多少缓存单元，time统计查字典的次数
    queue<int> use;
    cin >> m >> n;
    vector<int> a(1001, -1);//可以理解a为缓存
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        if (a[w] != w) { //未命中
            time++;
            if (cache < m) { //缓存没满
                a[w] = w;//加入缓存
                use.push(w);//加入字典
                cache++;
            } else if (cache >= m) {
                a[use.front()] = -1;
                use.pop();
                a[w] = w;
                use.push(w);//因为移去了一个缓存单元又加进来一个，所以cache值不变，所以不用cache--
            }
        }
    }
    cout << time;
}