hdu 2828 Buy Tickets（线段树）

一道不算复杂的线段树，就是数据处理需要好好想一下。

将输入的所有数据从后往前输入，对于最后一个值，如果它想插入第i个位置，那么他就必须在前面留下i-1个位置。对于倒数第二个人，如果他想插入j位置，那么在他前面就应该有j-1个空位置。他在最后一个人前面还是后面根本不重要，重要的是他必须在第j个空位。这个要好好想一下。

线段树节点存储的是当前区间的空位置的数量。

#include<stdio.h>

#include<string.h>

#define N 200005

struct node

{

	int x,y;

	int sum;

}a[N*3];

int aa[N],b[N],ans[N];

void Bulid_Tree(int t,int x,int y)

{

	a[t].x=x;

	a[t].y=y;

	a[t].sum=y-x+1;

	if(x==y)

		return ;

	int temp=t*2;

	int mid=(x+y)/2;

	Bulid_Tree(temp,x,mid);

	Bulid_Tree(temp+1,mid+1,y);

	return ;

}

void Insert_Tree(int t,int x,int y)

{

	if(a[t].x==a[t].y)

	{

		a[t].sum--;

		ans[a[t].x]=y;

		return ;

	}

	int temp=t*2;

	if(x>a[temp].sum)

	{

		x-=a[temp].sum;

		Insert_Tree(temp+1,x,y);

	}

	else

		Insert_Tree(temp,x,y);

	a[t].sum=a[temp].sum+a[temp+1].sum;

}

int main()

{

	int n;

	while(scanf("%d",&n)!=EOF)

	{

		Bulid_Tree(1,1,n);

		int i;

		for(i=0;i<n;i++)

			scanf("%d%d",&aa[i],&b[i]);

		for(i=n-1;i>=0;i--)

		{

			int x;

			x=aa[i]+1;

			Insert_Tree(1,x,b[i]);

		}

		for(i=1;i<n;i++)

			printf("%d ",ans[i]);

		printf("%d\n",ans[i]);

	}

	return 0;

}

巴特西

hdu 2828 Buy Tickets（线段树）

最新文章

热门文章