题目
- 原题地址：[JSOI2010]缓存交换
- 题目编号：NC20185
- 题目类型：堆、贪心
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 262144K，其他语言524288K
1.题目大意
- Cache容量以及主存单元访问次序一致，求最少的非命中次数
2.题目分析
- 每次删除缓存区中元素中下一次出现最晚的
3.题目代码
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int f[100005];
int nex[100005];
int main() {
int n, m;
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
map<int, int> mp;
priority_queue<int> q;
for(int i=n;i>0;i--) {
if(mp.count(a[i])) nex[i] = mp[a[i]];
else nex[i] = 100001;
mp[a[i]] = i;
}
int ans = 0;
for(int i=1;i<=n;i++) {
if(!f[i]){
ans++;
if(ans>m) f[q.top()] = 0, q.pop();
}
f[nex[i]] = 1, q.push(nex[i]);
}
cout << ans << endl;
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/282625.html