1 条题解
-
0
有限缓存:解题说明
用
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
- 上传者