比赛 |
20160407树结构练习 |
评测结果 |
TTTTT |
题目名称 |
树 |
最终得分 |
0 |
用户昵称 |
ZXCVBNM_1 |
运行时间 |
15.005 s |
代码语言 |
C++ |
内存使用 |
0.37 MiB |
提交时间 |
2016-04-07 20:02:13 |
显示代码纯文本
- #include<bits/stdc++.h>
- using namespace std;
- #define INF 1e9
- int q1[10010],q2[10010],L[10010],R[10010],MIN,MINI;
- int Build(int l1,int r1,int l2,int r2)
- {
- if(l1>r1)return 0;
- int rt=q2[r2],i=l1,cnt;
- while(q1[i]!=rt)i++;
- cnt=i-l1;
- L[rt]=Build(l1,i-1,l2,l2+cnt-1);
- R[rt]=Build(i+1,r1,l2+cnt,r2-1);
- return rt;
- }
- void dfs(int k,int tot)
- {
- if(L[k]==0&&R[k]==0)
- {
- if(tot<MIN)
- {
- MIN=tot;
- MINI=k;
- }
- else if(tot==MIN&&k<MINI)MINI=k;
- return;
- }
- if(L[k]!=0)dfs(L[k],tot+L[k]);
- if(R[k]!=0)dfs(R[k],tot+R[k]);
- }
- int main()
- {
- freopen("sumtree.in","r",stdin);
- freopen("sumtree.out","w",stdout);
- int n,root,sum,i;
- char ch;
- while(scanf("%d",&q1[1])==1)
- {
- n=0;
- //memset(q1,0,sizeof(q1));
- //memset(q2,0,sizeof(q2));
- sum=0;
- ch=getchar();
- for(i=2;;i++)
- {
- if(ch=='\n')break;
- scanf("%d",&q1[i]);
- ch=getchar();
- //if(ch=='\n')break;
- /*scanf("%c",&ch);
- if(ch==' '){q1[++n]=sum;sum=0;}
- else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
- else break;*/
- }
- n=i-1;
- //if(sum!=0)q1[++n]=sum;
- //n=0;sum=0;
- //while(1)
- for(i=1;i<=n;i++)
- {
- scanf("%d",&q2[i]);
- ch=getchar();
- /*scanf("%c",&ch);
- if(ch==' '){q2[++n]=sum;sum=0;}
- else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
- else break;*/
- }
- //if(sum!=0)q2[++n]=sum;
- root=Build(1,n,1,n);
- MIN=INF;MINI=0;
- dfs(root,root);
- printf("%d\n",MINI);
- }
- fclose(stdin);
- fclose(stdout);
- return 0;
- }