1 条题解

  • 0
    @ 2026-11-16 20:48:26

    有限缓存:解题说明

    用 queue<long long> 维护进入顺序,用 unordered_set<long long> 判断键是否已缓存。

    先用 find 检查命中。命中直接处理下一请求。未命中则计数加一;m=0 时直接结束本次处理。否则,当 queue::size() 等于容量时,将 front() 从集合删除并 pop(),再将新键 push() 到队尾并 insert() 到集合。

    两个容器始终保存同一批键,队列顺序就是要求的最终顺序。一次未命中最多淘汰一个旧键,每个请求期望 O(1),总期望时间 O(n),空间 O(min(m,n))。

    常见错误:命中后移动到末尾而变成 LRU;容量为 0 仍然访问队头;淘汰队列项却忘记从集合删除;通过集合遍历输出最终顺序。

    验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int m,n; cin>>m>>n;
        queue<long long> fifo;
        unordered_set<long long> resident;
        resident.reserve(2*min(m,n)+1);
        int misses=0;
        for(int i=0;i<n;++i) {
            long long key; cin>>key;
            if(resident.find(key)!=resident.end()) continue;
            ++misses;
            if(m==0) continue;
            if((int)fifo.size()==m) { resident.erase(fifo.front()); fifo.pop(); }
            fifo.push(key); resident.insert(key);
        }
        cout<<misses<<'\n'<<fifo.size();
        while(!fifo.empty()) { cout<<' '<<fifo.front(); fifo.pop(); }
        cout<<'\n';
        return 0;
    }
    
    
    • 1

    信息

    ID
    5267
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者