比赛 20160407树结构练习 评测结果 AAAAA
题目名称 最终得分 100
用户昵称 烟雨 运行时间 0.010 s
代码语言 C++ 内存使用 0.50 MiB
提交时间 2016-04-07 19:30:12
显示代码纯文本
#include<fstream>
#include<cstring>
#include<sstream>
#include<algorithm>
using namespace std;
ifstream cin("sumtree.in");
ofstream cout("sumtree.out");
int n=0,s1[10001],s2[10001],best=10001*10001,best_tree=0,pt=1;
class node
{public:
int at,lchild,rchild;
}tree[10001];
int clean()
{
for(int i=0;i<=10000;i++)
s1[i]=s2[i]=tree[i].at=tree[i].lchild=tree[i].rchild=0;
pt=1;
best=10001*10001;
best_tree=0;
return 0;
}
int read(int p[])
{
string s="";
int x,i;
if(!getline(cin,s))
return 0;
stringstream fin(s);
i=0;
while(fin>>x)
p[++i]=x;
n=i;
return i;
}
int find_root(int i)
{
int a;
for(a=1;a<=n;a++)
if(s1[a]==i)
break;
return a;
}
int build_tree(int root,int li,int ri,int lp,int rp)
{
int p=find_root(s2[rp]);
tree[root].at=s1[p];
if(p<=li)
tree[root].lchild=0;
else
{
tree[root].lchild=++pt;
build_tree(pt,li,p-1,lp,lp+(p-li)-1);
}
if(p>=ri)
tree[root].rchild=0;
else
{
tree[root].rchild=++pt;
build_tree(pt,p+1,ri,lp+(p-li),rp-1);
}
return 0;
}
int dfs_best(int x,int sum)
{
sum+=tree[x].at;
if(tree[x].lchild==0&&tree[x].rchild==0&&sum<=best)
{
if(sum<best)
{
best=sum;
best_tree=tree[x].at;
}
if(sum==best)
best_tree=min(tree[x].at,best_tree);
}
if(tree[x].lchild>0||tree[x].rchild>0)
{
if(tree[x].lchild)dfs_best(tree[x].lchild,sum);
if(tree[x].rchild)dfs_best(tree[x].rchild,sum);
}
return best_tree;
}
int main()
{
while(read(s1)&&read(s2))
{
build_tree(1,1,n,1,n);
cout<<dfs_best(1,0)<<endl;
clean();
}
cin.close();
cout.close();
return 0;
}