#STL014. 有限缓存
有限缓存
有限缓存
展厅终端只能记住最近进入缓存的 m 个资源键。每次有人请求一个键:若它已经在缓存中,本次命中,缓存顺序保持不变;若不在,本次未命中。容量大于 0 时,未命中的键会进入缓存,空间不足就先删除最早进入的键。
处理全部请求,报告未命中次数和最终缓存内容。缓存初始为空,容量可以为 0;容量为 0 时,每次请求都未命中,也不保存键。
输入格式
第一行两个整数 m、n,分别是缓存容量和请求数。第二行 n 个整数,按请求发生顺序给出资源键。
输出格式
第一行输出未命中次数。第二行先输出最终缓存大小 k,再输出 k 个键,顺序为最早进入到最晚进入。空缓存时第二行只输出 0。
数据范围与约定
- 0≤m≤200000,1≤n≤200000。
- 每个键在 [−1000000000,1000000000] 中。
- 键可重复。缓存中同一个键至多保存一份。
- 命中不改变进入顺序。本题使用 FIFO 规则。
样例 1
输入:
2 6
4 8 4 9 8 9
输出:
3
2 8 9
说明:请求 4、8 分别未命中,缓存为 [4,8];再次请求 4 不改变顺序。请求 9 时淘汰 4,缓存变为 [8,9];后两次都命中,因此共 3 次未命中。
样例 2
输入:
0 4
5 5 -1 5
输出:
4
0
说明:容量为 0,即使同一个键反复出现也不能缓存。四次请求全部未命中,最终大小为 0。
原创说明
本题的场景、题面、样例、实现与数据由本题单作者独立编写;仅使用公开的算法概念与 C++ 标准库接口,未使用第三方题面或测试文件。