1826: [JSOI2010]缓存交换
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 783 Solved: 439
[Submit][Status][Discuss]
Description
在计算机中，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缺失次数。
Input
输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。
Output
输出一行，为Cache缺失次数的最小值。
Sample Input
6 2
1 2 3 1 2 3
1 2 3 1 2 3
Sample Output
4
HINT
在第4次缺失时将3号单元换出Cache。
Source
JSOI2010第二轮Contest2
【题解】
每次选择下一个调用位置最远的交换出去
用堆实现，很多细节，见代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> ?6 #include <map> 7 #include <queue> 8 #define max(a, b) ((a) > (b) ? (a) : (b)) ?9 #define min(a, b) ((a) < (b) ? (a) : (b))10 11 inline void read(long long &x)12 {13 ????x = 0;char ch = getchar(), c = ch;14 ????while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar();15 ????while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();16 ????if(c == ‘-‘)x = -x;17 }18 19 const long long MAXN = 100000 + 10;20 21 long long n,m,num[MAXN],cnt[MAXN],nxt[MAXN],ans,chuxian[MAXN],sum;22 23 bool cmp(long long a, long long b)24 {25 ????return num[a] < num[b];26 }27 28 struct cmpp29 {30 ????bool operator()(long long a, long long b)31 ????{32 ????????return nxt[a] < nxt[b];33 ????}34 };35 36 std::priority_queue <int, std::vector<int>, cmpp> q;37 38 int main()39 {40 ????read(n), read(m);41 ????for(register long long i = 1;i <= n;++ i)42 ????????read(num[i]), cnt[i] = i;43 ????std::sort(cnt + 1, cnt + 1 + n, cmp);44 ????long long tot = 1, pre = num[cnt[1]];45 ????num[cnt[1]] = tot;46 ????for(register long long i = 2;i <= n;++ i)47 ????????if(num[cnt[i]] == pre)num[cnt[i]] = tot;48 ????????else ++ tot, pre = num[cnt[i]], num[cnt[i]] = tot;49 ????memset(cnt, 0, sizeof(cnt));50 ????memset(nxt, 0x3f, sizeof(nxt));51 ????for(register long long i = n;i >= 1;-- i)52 ????{53 ????????if(cnt[num[i]])nxt[i] = cnt[num[i]];54 ????????cnt[num[i]] = i;55 ????}56 ????memset(cnt, 0, sizeof(cnt));57 ????58 ????///cnt[i]表示i这个数是否在堆中以及i在原数组中的位置，chuxian[i]表示原数组i元素是否在堆中 59 ????for(register long long i = 1;i <= n;++ i)60 ????{61 ????????if(cnt[num[i]])62 ????????{63 ????????????q.push(i);64 ????????????chuxian[cnt[num[i]]] = 0;65 ????????????chuxian[i] = 1; 66 ????????}67 ????????else68 ????????{69 ????????????if(sum < m)q.push(i), cnt[num[i]] = i, chuxian[i] = 1, ++ans, ++sum;70 ????????????else71 ????????????{72 ????????????????while(chuxian[q.top()] == 0)q.pop();73 ????????????????cnt[num[q.top()]] = 0;74 ????????????????chuxian[q.top()] = 0;75 ????????????????q.pop();76 ????????????????q.push(i);77 ????????????????chuxian[i] = 1;78 ????????????????cnt[num[i]] = i;79 ????????????????++ ans;80 ????????????}81 ????????}82 ????}83 ????printf("%lld", ans);84 ????return 0;85 } BZOJ1826: [JSOI2010]缓存交换
原文地址：http://www.cnblogs.com/huibixiaoxing/p/7642231.html