Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
116994 | 陈家宝 | 最小叶节点 | C++ | 通过 | 100 | 0 MS | 280 KB | 715 | 2023-12-21 13:37:22 |
#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; }