比赛 20160407树结构练习 评测结果 TTTTT
题目名称 最终得分 0
用户昵称 ZXCVBNM_1 运行时间 15.005 s
代码语言 C++ 内存使用 0.37 MiB
提交时间 2016-04-07 20:02:13
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define INF 1e9
  4. int q1[10010],q2[10010],L[10010],R[10010],MIN,MINI;
  5. int Build(int l1,int r1,int l2,int r2)
  6. {
  7. if(l1>r1)return 0;
  8. int rt=q2[r2],i=l1,cnt;
  9. while(q1[i]!=rt)i++;
  10. cnt=i-l1;
  11. L[rt]=Build(l1,i-1,l2,l2+cnt-1);
  12. R[rt]=Build(i+1,r1,l2+cnt,r2-1);
  13. return rt;
  14. }
  15. void dfs(int k,int tot)
  16. {
  17. if(L[k]==0&&R[k]==0)
  18. {
  19. if(tot<MIN)
  20. {
  21. MIN=tot;
  22. MINI=k;
  23. }
  24. else if(tot==MIN&&k<MINI)MINI=k;
  25. return;
  26. }
  27. if(L[k]!=0)dfs(L[k],tot+L[k]);
  28. if(R[k]!=0)dfs(R[k],tot+R[k]);
  29. }
  30. int main()
  31. {
  32. freopen("sumtree.in","r",stdin);
  33. freopen("sumtree.out","w",stdout);
  34. int n,root,sum,i;
  35. char ch;
  36. while(scanf("%d",&q1[1])==1)
  37. {
  38. n=0;
  39. //memset(q1,0,sizeof(q1));
  40. //memset(q2,0,sizeof(q2));
  41. sum=0;
  42. ch=getchar();
  43. for(i=2;;i++)
  44. {
  45. if(ch=='\n')break;
  46. scanf("%d",&q1[i]);
  47. ch=getchar();
  48. //if(ch=='\n')break;
  49. /*scanf("%c",&ch);
  50. if(ch==' '){q1[++n]=sum;sum=0;}
  51. else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
  52. else break;*/
  53. }
  54. n=i-1;
  55. //if(sum!=0)q1[++n]=sum;
  56. //n=0;sum=0;
  57. //while(1)
  58. for(i=1;i<=n;i++)
  59. {
  60. scanf("%d",&q2[i]);
  61. ch=getchar();
  62. /*scanf("%c",&ch);
  63. if(ch==' '){q2[++n]=sum;sum=0;}
  64. else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
  65. else break;*/
  66. }
  67. //if(sum!=0)q2[++n]=sum;
  68. root=Build(1,n,1,n);
  69. MIN=INF;MINI=0;
  70. dfs(root,root);
  71. printf("%d\n",MINI);
  72. }
  73. fclose(stdin);
  74. fclose(stdout);
  75. return 0;
  76. }