RE 求助
  • 板块UVA548 树 Tree
  • 楼主hewo
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/8/8 11:09
  • 上次更新2023/11/6 20:57:37
查看原帖
RE 求助
64976
hewo楼主2020/8/8 11:09
#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 数组很大了

我认为可能是输入的问题,但调不出来,求大佬看看

2020/8/8 11:09
加载中...