#include<bits/stdc++.h>//in&post
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int inorder[10005],postorder[10005];//inorder中序,postorder后序
int tree[100005];//二叉树
inline void build(int inl,int inr,int postl,int postr,int i)
{
if(inr<inl) return ;
if(inl==inr)
{
tree[i]=postorder[postr];
return ;
}
int x=postorder[postr];
int wz;
tree[i]=x;
for(int k=inl;k<=inr;k++)
{
if(x==inorder[k])
{
wz=k;
break;
}
}
int p=wz-inl;
build(inl,wz-1,postl,postl+p-1,i*2);
build(wz+1,inr,postl+p,postr-1,i*2+1);
}//建树过程
int minn=0x7fffffff,ans=0x7fffffff;
inline void dfs(int i,int sum)
{
if(tree[i]==-1) return ;
if(tree[i*2]==-1&&tree[i*2+1]==-1)
{
if(sum<=minn)
{
sum=min(minn,sum);
ans=min(ans,tree[i]);
return ;
}
}
dfs(i*2,sum+tree[i*2]);
dfs(i*2+1,sum+tree[i*2+1]);
}//找答案
int main()
{
int in;
int cnt=0;
int in1;
char in2;
while(scanf("%d%c",&in1,&in2)!=-1)
{
cnt=1;
memset(tree,-1,sizeof(tree));
memset(inorder,0,sizeof(inorder));
memset(postorder,0,sizeof(postorder));
minn=0x7fffffff,ans=0x7fffffff;//更新数据
inorder[1]=in1;
do
{
scanf("%d%c", &in1,&in2);
inorder[++cnt]=in1;
if(in2=='\n') break;
if(in2==EOF)
{
return 0;
}
}while(in2!='\n');
//for(int i=1;i<=cnt;i++) cout<<inorder[i]<<" ";
cnt=0;
do
{
scanf("%d%c", &in1,&in2);
postorder[++cnt]=in1;
if(in2=='\n') break;
}while(in2!='\n');
//cout<<"OK"<<endl;
//奇怪的输入
build(1,cnt,1,cnt,1);
// cout<<"OK"<<endl;
// for(int i=1;i<=cnt;i++)
// {
// cout<<tree[i]<<" "<<tree[i*2]<<" "<<tree[i*2+1]<<endl;
// }
dfs(1,tree[1]);
cout<<ans<<endl;
}
return 0;
}
RT 数组很大了
我认为可能是输入的问题,但调不出来,求大佬看看