[蓝桥杯2019初赛]完全二叉树的权值

时间: 1 Sec 内存: 256 MB
题目描述
给定一棵包含N 个节点的完全二叉树，树上每个节点都有一个权值，按从
上到下、从左到右的顺序依次是A1, A2, AN，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是1。
输入
第一行包含一个整数N。
第二行包含N 个整数A1, A2, AN
对于所有评测用例，1<=N<=100000, -100000<=Ai<=100000。
输出
输出一个整数代表答案。
样例输入

7
1 6 5 4 3 2 1

样例输出

2

每一层的权值用long long 去存储，不会溢出，另外不能把最大值初始化为0，因为有最大值可能为负数。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[101000];
int p(int x){
	int t=1;
	while(x--)  t*=2;
	 return t;
}
int main()
{
	int n,t=1,i=2,j=2;
	scanf("%d %d",&n,&a[1]);
	long long maxx=a[1];
	for(int i=2;i<=n;i++) scanf("%d",&a[i]);
	while(i<=n){
		long long k=0;
	  for(;i<p(j)&&i<=n;i++)  k+=a[i];
	if(k>maxx)   maxx=k,t=j;
	j++;
	//cout<<k<<endl;
  }
   cout<<t<<endl;
   return 0;
}