| 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 |
|
输出示例
|
|
4
|
题解：有一个"很显然"的结论：窝萌要删集合中下一次出现时间尽量靠后的元素是极好的= =，于是弄个堆维护一下就行。。。还有个小技巧：讨论时的第一种情况只要添加就可以了，因为next明显是递增的，以后不会访问到原先的点，也就不用再删除了。
（懒得用set写了treap= =）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<2;d++)if(ch[d])
using namespace std;
const int maxn=+,maxnode=+,inf=-1u>>;
struct data{int nxt,p;}x[maxn];
bool operator<(const data&a,const data&b){return a.nxt<b.nxt;}
priority_queue<data>Q;int next[maxn],A[maxn];
inline int read(){
int x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
struct node{
node*ch[];int r,siz,v;
void init(){r=rand();siz=;ch[]=ch[]=NULL;}
void update(){siz=;CH{siz+=ch[d]->siz;}return;}
}treap[maxnode],*nodecnt=treap,*root;queue<node*>R;
node*neawnode(){node*k;if(R.empty())k=nodecnt++;else k=R.front(),R.pop();k->init();return k;}
void del(node*&x){R.push(x);x=NULL;return;}
void rotate(node*&x,int d){
node*k=x->ch[d^];x->ch[d^]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;
}
void insert(node*&x,int v){
if(!x)x=nodecnt++,x->init(),x->v=v;
else{int d=v>x->v;insert(x->ch[d],v);
if(x->r<x->ch[d]->r)rotate(x,d^);else x->update();
}return;
}
void remove(node*&x,int v){
if(x->v==v){
if(x->ch[]&&x->ch[]){
int d=x->ch[]->r>x->ch[]->r;
rotate(x,d);remove(x->ch[d],v);
}else{node*k;x=x->ch[]?x->ch[]:x->ch[];del(k);}
}else remove(x->ch[v>x->v],v);
if(x)x->update();return;
}
void print(node*x){
if(!x)return;print(x->ch[]);printf("%d ",x->v);print(x->ch[]);return;
}
bool num(node*x,int v){
if(!x)return false;
if(x->v==v)return true;
if(v>x->v)return num(x->ch[],v);
else return num(x->ch[],v);
}
int n,m,b[maxn];
int main(){
int tp;
n=read();m=read();
for(int i=;i<=n;i++){x[i].nxt=read();x[i].p=i;}
sort(x+,x+n+);int cur=;
for(int i=;i<=n;i++){
if((i==)||(x[i].nxt!=x[i-].nxt))cur++;A[x[i].p]=cur;
}
for(int i=n;i;i--){
if(b[A[i]]==)next[i]=n+;
else next[i]=b[A[i]];
b[A[i]]=i;
}int ans=;
for(int i=;i<=n;i++){
if(root&&num(root,A[i]))Q.push((data){next[i],A[i]});
else if(!root||root->siz<m){Q.push((data){next[i],A[i]});insert(root,A[i]);ans++;}
else{remove(root,(Q.top()).p);Q.pop();Q.push((data){next[i],A[i]});insert(root,A[i]);ans++;}
}write(ans);
return ;
}