| ||||||||||
| 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