蓝桥杯完全二叉树的权值

二叉树的权值"/>

蓝桥杯完全二叉树的权值

【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从
上到下、从左到右的顺序依次是 A 1 , A 2 , ··· A N ，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A 1 , A 2 , ··· A N 。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1
试题G: 完全二叉树的权值 10
第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ A i ≤ 100000。

#include <stdio.h>
int deep(int s){int flag=0;while(s>0){s=s/2;flag++;}return flag;
}
int main(){int n;scanf("%d",&n);int k = deep(n);//树的深度 int sum[k]={0};int deepnum=0;for(int i =0; i<n;i++){int t = deep(i+1);int num;scanf("%d",&num);sum[t]=sum[t]+num; }int max=0;for(int i=0;i<k;i++){//	printf("%d ",sum[i+1]);if(sum[i]>max){max=sum[i];deepnum=i;}}printf("%d",deepnum);return 0;
}