COJ 2108 Day7-例1

Day7-例1

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

在计算机中，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缺失次数。

输入

输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

输出

输出一行，为Cache缺失次数的最小值。

输入示例

6 2
1 2 3 1 2 3

输出示例

题解：有一个"很显然"的结论：窝萌要删集合中下一次出现时间尽量靠后的元素是极好的= =，于是弄个堆维护一下就行。。。还有个小技巧：讨论时的第一种情况只要添加就可以了，因为next明显是递增的，以后不会访问到原先的点，也就不用再删除了。

（懒得用set写了treap= =）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<stack>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 #define CH for(int d=0;d<2;d++)if(ch[d])
11 using namespace std;
12 const int maxn=100000+10,maxnode=200000+10,inf=-1u>>1;
13 struct data{int nxt,p;}x[maxn];
14 bool operator<(const data&a,const data&b){return a.nxt<b.nxt;}
15 priority_queue<data>Q;int next[maxn],A[maxn];
16 inline int read(){
17     int x=0,sig=1;char ch=getchar();
18     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0;
19     for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';
20     return sig?x:-x;
21 }
22 inline void write(int x){
23     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
24     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
25     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
26 }
27 struct node{
28     node*ch[2];int r,siz,v;
29     void init(){r=rand();siz=1;ch[0]=ch[1]=NULL;}
30     void update(){siz=1;CH{siz+=ch[d]->siz;}return;}
31 }treap[maxnode],*nodecnt=treap,*root;queue<node*>R;
32 node*neawnode(){node*k;if(R.empty())k=nodecnt++;else k=R.front(),R.pop();k->init();return k;}
33 void del(node*&x){R.push(x);x=NULL;return;}
34 void rotate(node*&x,int d){
35     node*k=x->ch[d^1];x->ch[d^1]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;
36 }
37 void insert(node*&x,int v){
38     if(!x)x=nodecnt++,x->init(),x->v=v;
39     else{int d=v>x->v;insert(x->ch[d],v);
40         if(x->r<x->ch[d]->r)rotate(x,d^1);else x->update();
41     }return;
42 }
43 void remove(node*&x,int v){
44     if(x->v==v){
45         if(x->ch[0]&&x->ch[1]){
46             int d=x->ch[0]->r>x->ch[1]->r;
47             rotate(x,d);remove(x->ch[d],v);
48         }else{node*k;x=x->ch[0]?x->ch[0]:x->ch[1];del(k);}
49     }else remove(x->ch[v>x->v],v);
50     if(x)x->update();return;
51 }
52 void print(node*x){
53     if(!x)return;print(x->ch[0]);printf("%d ",x->v);print(x->ch[1]);return;
54 }
55 bool num(node*x,int v){
56     if(!x)return false;
57     if(x->v==v)return true;
58     if(v>x->v)return num(x->ch[1],v);
59     else return num(x->ch[0],v);
60 }
61 int n,m,b[maxn];
62 int main(){
63     int tp;
64     n=read();m=read();
65     for(int i=1;i<=n;i++){x[i].nxt=read();x[i].p=i;}
66     sort(x+1,x+n+1);int cur=0;
67     for(int i=1;i<=n;i++){
68         if((i==1)||(x[i].nxt!=x[i-1].nxt))cur++;A[x[i].p]=cur;
69     }
70     for(int i=n;i;i--){
71         if(b[A[i]]==0)next[i]=n+1;
72         else next[i]=b[A[i]];
73         b[A[i]]=i;
74     }int ans=0;
75     for(int i=1;i<=n;i++){
76         if(root&&num(root,A[i]))Q.push((data){next[i],A[i]});
77         else if(!root||root->siz<m){Q.push((data){next[i],A[i]});insert(root,A[i]);ans++;}
78         else{remove(root,(Q.top()).p);Q.pop();Q.push((data){next[i],A[i]});insert(root,A[i]);ans++;}
79     }write(ans);
80     return 0;
81 }