经典页面调度问题，理想算法就是移出从现在开始最久未使用的。
线段树中存正在使用的页面（题中是模版。。）下次出现的时间，每次选出现时间最晚的扔掉。如果遇到一个已经在内存中的页面，也要跟新该页面在线段树中的值。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #define lson l,m,p<<1 5 #define rson m+1,r,p<<1|1 6 #define calm l+r>>1 7 #define MAXN 100005 8 int n,m,x[MAXN]; 9 int ld[MAXN],next[MAXN],pos[MAXN],has[MAXN]; 10 int maxv[MAXN<<2],maxid[MAXN<<2]; 11 int binser(int x){ 12 int min=1,max=n+1,mid=min+max>>1; 13 for(;mid!=min;mid=min+max>>1){ 14 if(ld[mid]<=x)min=mid; 15 else max=mid; 16 } 17 return ld[mid]==x?mid:-1; 18 } 19 void pushup(int p){ 20 if(maxv[p<<1]>maxv[p<<1|1]) 21 maxv[p]=maxv[p<<1],maxid[p]=maxid[p<<1]; 22 else 23 maxv[p]=maxv[p<<1|1],maxid[p]=maxid[p<<1|1]; 24 } 25 void update(int L,int v,int l,int r,int p){ 26 if(l==r){ 27 maxv[p]=v,maxid[p]=L; 28 return; 29 } 30 int m=calm; 31 if(L<=m)update(L,v,lson); 32 if(L>m)update(L,v,rson); 33 pushup(p); 34 } 35 int solve(){ 36 memset(has,0,sizeof has); 37 memset(maxv,0,sizeof maxv); 38 int rel=0; 39 for(int i=1;i<=m;i++){ 40 int id=binser(i); 41 if(id==-1){rel++;continue;} 42 update(id,pos[id],1,n,1); 43 has[id]=1; 44 } 45 int ans=0; 46 for(int i=1;i<=n;i++){ 47 int id=x[i]; 48 if(has[id]==0){ 49 update(id,next[i],1,n,1); 50 has[id]=1; 51 ans++; 52 //考虑先把没用的丢掉(一直没有的) 53 if(rel){rel--;continue;} 54 //将最远未出现的丢掉 55 has[maxid[1]]=0; 56 update(maxid[1],0,1,n,1); 57 }else{ 58 update(id,next[i],1,n,1); 59 } 60 } 61 return ans; 62 } 63 void getnext(){ 64 memset(pos,0x3f,sizeof pos); 65 for(int i=n;i>=1;i--){ 66 next[i]=pos[x[i]]; 67 pos[x[i]]=i; 68 } 69 } 70 71 int main(){ 72 //freopen("test.in","r",stdin); 73 while(scanf("%d%d",&n,&m)!=EOF){ 74 for(int i=1;i<=n;i++) 75 scanf("%d",&x[i]),ld[i]=x[i]; 76 std::sort(ld+1,ld+n+1); 77 for(int i=1;i<=n;i++)x[i]=binser(x[i]); 78 getnext(); 79 int x=solve(); 80 printf("%d\n",x); 81 } 82 return 0; 83 }