自己做网站微商,手机网站一般多宽,备案中心查网站,南平市住房和城乡建设局网站一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 802A - Codeforces 二、解题报告
1、思路分析
这个题相当于你有一个容量为K的Cache#xff0c;然后给你一系列访存序列
当访问缺失时你不得不替换掉Cache中某些块
学过操作系统都很熟悉页面置…一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 802A - Codeforces 二、解题报告
1、思路分析
这个题相当于你有一个容量为K的Cache然后给你一系列访存序列
当访问缺失时你不得不替换掉Cache中某些块
学过操作系统都很熟悉页面置换算法里面有个预言家算法最佳置换算法
即我们不得不替换时选择替换掉将来最晚被访问的块这样能够最大限度下降低缺页率
换到本题我们不得不扔掉某些书的时候我们扔掉最晚被借用的书这样更能够让别的书发挥其作用降低代价到最低为什么这样正确呢我们每次访问无非访问成功或者访问缺失我们这样最大化了访问成功自然最小化了访问缺失
2、复杂度 时间复杂度 O(nlogn)空间复杂度O(n) 3、代码详解
#include bits/stdc.h
using PII std::pairint, int;
using i64 long long;const int inf 1e9;void solve() {int N, K, res 0;std::cin N K;std::vectorint a(N);std::mapint, std::vectorint pos;std::unordered_setint buf;std::priority_queuePII pq;for (int i 0; i N; i ) std::cin a[i];for (int i N - 1; ~i; i -- ) pos[a[i]].push_back(i);for (int i 0; i N; i ) {pos[a[i]].pop_back();if (buf.count(a[i])) {if (pos[a[i]].size()) pq.emplace(pos[a[i]].back(), a[i]);else buf.erase(a[i]);continue;}while (pq.size() !pos[pq.top().second].size()) pq.pop();if (buf.size() K) buf.erase(pq.top().second), pq.pop();if (pos[a[i]].size()) buf.insert(a[i]), pq.emplace(pos[a[i]].back(), a[i]);res ;}std::cout res;
}int main () {std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);int _ 1;// std::cin _;while (_ --)solve();return 0;
}
