| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
树状数组16MS……#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; int n; int fmc[10000],ans[10000]; int tr[10000],e[10000]; int e2; void init() { for(int i=1;i<=n;i++) { tr[i]=i&(-i); } } void rmv(int k) { for(;k<=n;k+=k&(-k)) { tr[k]--; } } int Get(int k) { int s=0,cnt=0; for(int a=1<<e2;a>0;a=a>>1) { if(s+a<=n&&cnt+tr[s+a]<=k) { if(cnt+tr[s+a]==k){ s+=a; for(;e[s]==1;s--);//这里要注意!1-s之间剩下k个数不代表第k个数就是s!被坑了近1h…… cnt+=tr[s]; break; } s+=a; cnt+=tr[s]; } } return s; } int main() { scanf("%d",&n); e2=log((double)n)/log((double)2); for(int i=2;i<=n;i++) scanf("%d",&fmc[i]); init(); for(int i=n;i>=1;i--) { int nm=Get(fmc[i]+1); rmv(nm); e[nm]=1; ans[i]=nm; } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator