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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

第一个线段树程序就不知道哪里错了,麻烦诸位大牛帮帮忙,谢谢。

Posted by hhhh at 2006-08-28 17:02:32 on Problem 2828
#include<iostream.h>

int B[400002],E[400002],C[400002];     //分别表示线段起点,终点,线段内1的个数
int person[200000][2];                 //进入队中的人
int result[200001];                    //结果序列

void Init(int begin,int end,int v)      //初始化线段树
{
	if(begin==end)                      //叶子
	{
		B[v]=begin;
		E[v]=end;
		C[v]=1;
	}
	else                         
	{
		B[v]=begin;
		E[v]=end;
		C[v]=end-begin+1;
		Init(begin,(begin+end)/2,2*v);
		Init((begin+end)/2+1,end,2*v+1);
	}
}

void change(int count,int value,int v) //用每个进入队伍的人调整线段树
{
	C[v]--;
	if(B[v]==E[v])                     
	{
		result[B[v]]=value;
		return;
	}
	if(C[2*v]>count)
	{
		change(count,value,2*v);
	}
	else
	{
		change(count-C[2*v],value,2*v+1);
	}
}
int main()
{
	int n,i;
	while(cin>>n)
	{
		Init(1,n,1);
		for(i=0;i<n;i++)
		{
			cin>>person[i][0]>>person[i][1];
		}
		for(i=n-1;i>=0;i--)
		{
			change(person[i][0],person[i][1],1);
		}
		for(i=1;i<n;i++)
		{
			cout<<result[i]<<' ';
		}
		cout<<result[i]<<endl;
	}
	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