[JSOI2010]缓存交换 题解
题目地址:洛谷:【P4404】[JSOI2010]缓存交换 – 洛谷、BZOJ:Problem 1826. — [JSOI2010]缓存交换
题目描述
在计算机中,CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时,则需要从主存里把数据调入Cache。此时,如果Cache容量已满,则必须先从中删除一个。
例如,当前Cache容量为3,且已经有编号为10和20的主存单元。 此时,CPU访问编号为10的主存单元,Cache命中。
接着,CPU访问编号为21的主存单元,那么只需将该主存单元移入Cache中,造成一次缺失(Cache Miss)。
接着,CPU访问编号为31的主存单元,则必须从Cache中换出一块,才能将编号为31的主存单元移入Cache,假设我们移出了编号为10的主存单元。
接着,CPU再次访问编号为10的主存单元,则又引起了一次缺失。我们看到,如果在上一次删除时,删除其他的单元,则可以避免本次访问的缺失。
在现代计算机中,往往采用LRU(最近最少使用)的算法来进行Cache调度——可是,从上一个例子就能看出,这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求,聪聪想知道如何在每次Cache缺失时换出正确的主存单元,以达到最少的Cache缺失次数。
题意简述
cache容量有限,当CPU想访问某一cache中不存在的数据时,如果cache已满,需要从中扔掉一块数据再读入,现在希望求出最小的这种cache miss的次数。
输入输出格式
输入格式:
输入文件第一行包含两个整数N和M(1<=M<=N<=100,000),分别代表了主存访问的次数和Cache的容量。
第二行包含了N个空格分开的正整数,按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。
输出格式:
输出一行,为Cache缺失次数的最小值。
输入输出样例
输入样例#1:
6 2 1 2 3 1 2 3
输出样例#1:
4
说明
在第4次缺失时将3号单元换出Cache。
题解
跟[POI2005]SAM-TOY CARS是一个题。只不过这里值域比较大需要离散化或者像我一样强行map/set用上去。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 500005;
std::set<int> inque;
int n, k, a[MAXN];
std::map<int, int> nxt, head;
struct cmp {
inline bool operator()(const int &a, const int &b) {
return nxt[a] < nxt[b];
}
};
std::priority_queue<int, std::vector<int>, cmp> pq;
int main() {
n = readint(); k = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint();
nxt[head[a[i]]] = i; head[a[i]] = i;
}
for(std::map<int, int>::iterator it = head.begin(); it != head.end(); it++) {
nxt[it->second] = 1e9;
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(!inque.count(a[i])) {
if(pq.size() == k) {
inque.erase(a[pq.top()]); pq.pop();
}
inque.insert(a[i]); ans++;
} else {
k++;
}
pq.push(i);
}
printf("%d", ans);
return 0;
}