比赛 |
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;
}