比赛 20160407树结构练习 评测结果 AAAAE
题目名称 最终得分 80
用户昵称 Lovelove_boii 运行时间 0.153 s
代码语言 C++ 内存使用 0.50 MiB
提交时间 2016-04-07 18:54:27
显示代码纯文本
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
ifstream cin("sumtree.in");
ofstream cout("sumtree.out");
const int M=10001;
int in[M],post[M],n=0,maxn=0,len=0,best_sum=M,best=M,pt,m;
class node
{public:
	int data,lk,rk;
}tree[M];
int init()
{
	pt=1;n=0;
	best_sum=10001*10001;
	best=10001;
	for(int i=0;i<=M;i++)
	{
		in[i]=0;
		post[i]=0;
		tree[i].data=tree[i].lk=tree[i].rk=0;
	}
	return 0;
}
int read(int p[])
{
	string s="";
	int x;
	if(!getline(cin,s))
		return 0;
	stringstream fin(s);
	n=0;
	while(fin>>x)
	p[++n]=x;
	fin.str("");
	return n>0;
}
int pos(int x)
{
	int i;
	for(i=1;i<=n;i++)
		if(in[i]==x)
			break;
	return i;
}
int buildtree(int root,int li,int ri,int lp,int rp)
{
	int p;
	p=pos(post[rp]);
	if(p<=li)
	tree[root].lk=0;
	else
	{
		tree[root].lk=post[rp-(ri-p)-1];
		buildtree(tree[root].lk,li,rp-(ri-p)-1,lp,rp-(ri-p)-1);
	}
	if(p>=ri)
		tree[root].rk=0;
	else
	{
		tree[root].rk=post[rp-1];
		buildtree(post[rp-1],p+1,ri,rp-(ri-p),rp-1);
	}
	return 0;
}
int dfs(int i,int wn)
{
	if(tree[i].lk==0&&tree[i].rk==0)
	{
		if(wn<=best_sum)
		{
			best_sum=wn;
			best=min(best,i);
		}
	}
	else
	{
		if(tree[i].lk)
		{
			dfs(tree[i].lk,++wn);
			--wn;
		}
		if(tree[i].rk)
		{
			dfs(tree[i].rk,++wn);
			--wn;
		}
	}
	return 0;
}
int main()
{
	init();
	while(read(in)&&read(post))
	{
		buildtree(post[n],1,n,1,n);
		dfs(post[n],0);
		cout<<best<<endl;
		init();
	}
	cin.close();
	cout.close();
	return 0;
}