完全二叉树的权值蓝桥杯,求二叉树的权值

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示:

现在pbdqd要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注:根的深度是 1。

输入
第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· AN。

输出
输出一个整数代表答案。

样例输入
7
1 6 5 4 3 2 1
样例输出
2

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int M=1000010;int inf=0x3f3f3f3f;int a[M],res[M];//a数组存数并且与前求和得到前缀和//res数组存储每一层的权值和 //前缀和：一串数字中自身和她前面数字的总和为前缀和//例：1 2 3 4 5 ->1 3 6 10 15//前缀和可以求区间的和//二叉树每一层最后一个节点的下标（位置）为上一层最后节点下标j *2+1；//例： 第二层最后一个节点下标 3 则第三层最后一个节点下标 j=3*2+1=7 //这样第三层的权值和就可以表示为 a[j]-a[j>>1] int main() {int i,j,k,l,m,n,s=0,max=-inf;memset(a,0,sizeof(a));scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);a[i]=a[i-1]+a[i];//求前缀和 }for(i=1,j=1;j<=n;i++,j=(j<<1)+1) //i为层数（深度）,j为每一层最后节点的下标 {res[i]=a[j]-a[j>>1];//res存储每一层的权值和,j>>1为上一层最后节点下标 }if((j>>1)<n) //当j的上一层坐标不为n的时候，说明最后一层没有满，求出最后一层未满的权值 res[i]=a[n]-a[j>>1];else//当为满二叉树时，将多出的层数剪掉 i--;for(k=1;k<=i;k++){if(res[k]>max)//寻找权值和最大的深度 {max=res[k];s=k;}}printf("%dn",s);return 0;}