B1826 [JSOI2010]缓存交换 贪心+离散化+堆

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 Input6 21 2 3 1 2 3Sample Output4HINT在第4次缺失时将3号单元换出Cache。SourceJSOI2010第二轮Contest2

#include<iostream>#include<cstdio>#include<cmath>#include<ctime>#include<queue>#include<algorithm>#include<cstring>using namespace std;#define duke(i,a,n) for(int i = a;i <= n;i++)#define lv(i,a,n) for(int i = a;i >= n;i--)#define clean(a) memset(a,0,sizeof(a))const int INF = 1 << 30;typedef long long ll;typedef double db;template <class T>void read(T &x){ ???char c; ???bool op = 0; ???while(c = getchar(), c < ‘0‘ || c > ‘9‘) ???????if(c == ‘-‘) op = 1; ???x = c - ‘0‘; ???while(c = getchar(), c >= ‘0‘ && c <= ‘9‘) ???????x = x * 10 + c - ‘0‘; ???if(op) x = -x;}template <class T>void write(T x){ ???if(x < 0) putchar(‘-‘), x = -x; ???if(x >= 10) write(x / 10); ???putchar(‘0‘ + x % 10);}struct node{ ???int nxt,w; ???bool operator < (const node &oth) const ???{ ???????return nxt < oth.nxt; ???}} a[200010];int num = 0,n,m,tot,ans = 0;int lst[200010];int vis[200010];int k[200010];priority_queue <node> qu;int main(){ ???read(n); ???read(m);// ???cout<<n<<endl; ???duke(i,1,n) ???{ ???????read(a[i].w); ???????k[i] = a[i].w; ???} ???sort(k + 1,k + n + 1); ???int f = unique(k + 1,k + n + 1) - k - 1; ???duke(i,1,n) ???{ ???????a[i].w = lower_bound(k + 1,k + f + 1,a[i].w) - k;// ???????cout<<a[i].w<<endl; ???} ???memset(lst,0x3f,sizeof(lst)); ???lv(i,n,1) ???{ ???????a[i].nxt = lst[a[i].w]; ???????lst[a[i].w] = i; ???} ???/*duke(i,1,n) ???printf("%d ",a[i].nxt); ???puts("");*/ ???duke(i,1,n) ???{ ???????if(vis[a[i].w] == 0) ???????{ ???????????if(tot >= m) ???????????{ ???????????????node f = qu.top();// ???????????????cout<<f.nxt<<" "<<f.w<<endl; ???????????????vis[f.w] = 0; ???????????????tot--; ???????????????qu.pop(); ???????????} ???????????qu.push(a[i]); ???????????vis[a[i].w] = 1; ???????????tot++; ???????????ans++; ???????} ???????else ???????{ ???????????qu.push(a[i]); ???????} ???} ???printf("%d\n",ans); ???return 0;}