首页 > 代码库 > ZSTU OJ 4272 最佳淘汰算法
ZSTU OJ 4272 最佳淘汰算法
线段树。
处理出每个位置下一个位置是哪里。然后搞个线段树找一下最大值就可以了。
#include<map>#include<set>#include<ctime>#include<cmath>#include<queue>#include<string>#include<stack>#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<functional>using namespace std; int n,m,a[500010];bool In[100010]; int Seg[400010],nx[500010],p[500010];int POS,sx[500010],A[500010]; void update(int p,int val,int l,int r,int rt){ if(l==r) { Seg[rt]=val; return ; } int m=(l+r)/2; if(p>=l&&p<=m) update(p,val,l,m,2*rt); else update(p,val,m+1,r,2*rt+1); Seg[rt] = max(Seg[2*rt],Seg[2*rt+1]);} void get(int l,int r,int rt){ if(l==r) { POS=l; return ; } int m=(l+r)/2; if(Seg[2*rt]>Seg[2*rt+1]) get(l,m,2*rt); else get(m+1,r,2*rt+1);} int main(){ while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<=100000;i++) p[i]=n+1; for(int i=n;i>=1;i--) nx[i] = p[a[i]], p[a[i]]=i; memset(In,0,sizeof In); memset(Seg,0,sizeof Seg); memset(sx,0,sizeof sx); memset(A,0,sizeof A); int sz=0; for(int i=1;i<=n;i++) { if(In[a[i]]) { update(a[i],nx[i],0,100000,1); continue; } if(sz<m) { sz++; A[sz]=a[i]; sx[a[i]]=sz; update(a[i],nx[i],0,100000,1); } else { get(0,100000,1); update(POS,0,0,100000,1); int t = sx[POS]; sx[POS]=0; In[POS]=0; update(a[i],nx[i],0,100000,1); sx[a[i]]=t; A[t]=a[i]; } In[a[i]]=1; } for(int i=1;i<=sz;i++) { printf("%d",A[i]); if(i<sz) printf(" "); else printf("\n"); } } return 0;}
ZSTU OJ 4272 最佳淘汰算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。