Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
143582 | 陈家宝 | 最小叶节点 | C++ | 通过 | 100 | 0 MS | 276 KB | 701 | 2024-04-16 17:01:17 |
#include<bits/stdc++.h> using namespace std; int lc[10010],rc[10010],n,t,zx[10010],hx[10010],idx,best; char c; int build(int l1,int r1,int l2,int r2,int sum){ if(l1>r1)return 0; int root=hx[r2],p=l1; while(zx[p]!=root)p++; int len=p-l1; sum+=root; lc[root]=build(l1,p-1,l2,l2+len-1,sum); rc[root]=build(p+1,r1,l2+len,r2-1,sum); if(!lc[root]&&!rc[root]&&((sum<best)||(sum==best&&root<idx))){ best=sum; idx=root; } return root; } int main(){ while(scanf("%d%c",&t,&c)!=EOF){ n=1; zx[1]=t; while(c!='\n')scanf("%d%c",&zx[++n],&c); for(int i=1;i<=n;i++)scanf("%d",&hx[i]); idx=best=0x7fffffff; build(1,n,1,n,0); printf("%d\n",idx); } return 0; }