P76060 先进先出缓存 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76060，不要直接用于外站同名题。

解题思路

队列维护缓存的进入先后顺序，set 判断是否已命中；未命中时若满则出队再入队。

复杂度

时间 $O(n\log m)$，空间 $O(m)$。

易错点

缓存命中不改变队列顺序，本题不是 LRU 缓存。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;
    cin>>m>>n;
    queue<int>q;
    set<int>st;
    int misses=0;
    while(n--){
        int x;
        cin>>x;
        if(st.count(x))continue;
        misses++;
        if((int)q.size()==m){
            st.erase(q.front());
            q.pop();
        }
        q.push(x);
        st.insert(x);
    }
    cout<<misses<<nl;
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。