Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树状数组16MS……

Posted by liu_cheng_ao at 2016-09-14 23:00:49 on Problem 2182
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator