比赛 20160407树结构练习 评测结果 AAAAA
题目名称 最终得分 100
用户昵称 ミント 运行时间 0.008 s
代码语言 C++ 内存使用 0.43 MiB
提交时间 2016-04-07 18:56:04
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>

#include <iostream>
#include <cstdio>
#include <sstream>

//#define Left 0
//#define Right 1
//#define In 0
//#define Post 1
//#define Leaves -1 

using namespace std;

ifstream fin("sumtree.in");
ofstream fout("sumtree.out");

const int Maxn = 10000 + 20;    
const int Maxm = 2 + 1;
const int INF = 0xfffff; 
int InArray[Maxn], PostArray[Maxn];
int lArray[2], Ans = INF, AnsNode;
int TreeKount = 1;
class poi
{
	public:
		int Child[Maxm];
		//int Father;
		int Value;
}Tree[Maxn];

void Init()
{
	memset(Tree, 0, sizeof(Tree));
	for(int i=1;i<=Maxn-1;i++)
		for(int j=1;j<=2;j++)
		Tree[i].Child[j] = -1;
	
	return ;
}
bool GetString(int Temp[], int Flag)
{
	string Str;
	int TempLength = 0;
	int TempNum = 0;
	
	if(!getline(fin, Str))
		return false;
	stringstream fin(Str);
	
	while(fin>>TempNum)
	{
		TempLength++;
		Temp[TempLength] = TempNum ;
	}
	//cout<<endl;
	lArray[Flag] = TempLength;
	
	//fout<<TempLength<<endl;
	
	return TempLength > 0;
}
void EmptyString(int Array[])
{
	for(int i=0;i<Maxn;i++)
		Array[i] = 0;
	return ;
}
int FindPos(int Array[], int ToFind)
{
	for(int i=1;i<=lArray[0];i++)
		if(Array[i]==ToFind)
			return i;
	//return -1;
}
/*int BuildTree(int In[], int Istart, int Iend, int Post[], int Pstart, int Pend)
{
	if(Istart<Iend&&Pstart<Pend)
	{
		int Now = Post[Pend];
		int RootPos = FindPos(In, Istart, Iend, Now);
		
		int Temp = RootPos - Istart;
		
		//TreeKount++;
		Tree[Now].Child[0] = BuildTree(In, Istart, Istart+Temp, Post, Pstart, Pstart+Temp);
		Tree[Now].Child[1] = BuildTree(In, Istart+Temp+1, Iend, Post, Pstart+Temp, Pend);
		
		return Now;
	}
	return -1;
}*/
void BuildTree(int Root, int In[], int Istart, int Iend, int Post[], int Pstart, int Pend)
{
	int Now = Post[Pend];
	int RootPos = FindPos(In, Now);
	int Temp = RootPos - Istart;
	
	Tree[Root].Value = In[RootPos];
	
	//fout<<RootPos<<endl;
	//fout<<Tree[Root].Value<<' ';
	
	//Left
	if(RootPos<=Istart)
		Tree[Root].Child[0] = -1;
	else
	{
		TreeKount++;
		Tree[Root].Child[0] = TreeKount;
		
		BuildTree(TreeKount, In, Istart, RootPos-1, Post, Pstart, Pstart+Temp-1);
	}
	//Right
	if(RootPos>=Iend)
		Tree[Root].Child[1] = -1;
	else
	{
		TreeKount++;
		Tree[Root].Child[1] = TreeKount;
		
		BuildTree(TreeKount, In, RootPos+1, Iend, Post, Pstart+Temp, Pend-1);
	}
	return ;
}
void DFS(int Pos, int Sum)
{
	Sum += Tree[Pos].Value;
	
	if(Tree[Pos].Child[0]!=-1)
		DFS(Tree[Pos].Child[0], Sum);
	if(Tree[Pos].Child[1]!=-1)
		DFS(Tree[Pos].Child[1], Sum);
	if(Tree[Pos].Child[0]==-1&&Tree[Pos].Child[1]==-1)
	{
		if(Ans>Sum)
		{
			Ans = Sum;
			AnsNode = Pos;
			//fout<<Pos<<endl;
		}
		if(Ans==Sum&&Tree[Pos].Value<Tree[AnsNode].Value)
			AnsNode = Pos;
	}
	
	return ;
}
void Work()
{
	while(GetString(InArray, 0)&&GetString(PostArray, 1))
	{		
		BuildTree(1, InArray, 1, lArray[0], PostArray, 1, lArray[1]);
		
		Ans = INF;
		
		DFS(1, 0);
		
		fout<<Tree[AnsNode].Value<<endl;
		//fout<<Ans<<endl;
		//fout<<"___________"<<endl;
		
		//fout<<lArray[1]<<endl;
		
		EmptyString(InArray);
		EmptyString(PostArray);
	}
	
	//for(int i=1;i<=lArray[0];i++)
		//fout<<Tree[i].Value<<": "<<Tree[i].Child[0]<<' '<<Tree[i].Child[1]<<endl;
	return ;
}
int main()
{
	Init();
	
	//Read();
	
	Work();
	
	//Write();
	
	fin.close();
	fout.close();
	
	return 0;
}