完全二叉树的权值
给定一棵包含 NN 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅ANA1,A2,···AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?
如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 11。
输入格式
第一行包含一个整数 NN。
第二行包含 NN 个整数 A1,A2,⋅⋅⋅ANA1,A2,···AN。
输出格式
输出一个整数代表答案。
数据范围
1≤N≤1051≤N≤105,
−105≤Ai≤105−105≤Ai≤105
输入样例:
7
1 6 5 4 3 2 1
输出样例:
2
代码展示
首先这是双指针类的问题,因为他的范围是10^5,所以根据判断应该是0(n),或者o(nlogn),这个时间复杂度,我们可以使用双指针算法进行解决。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 7 const int N=100010; 8 9 typedef long long LL; 10 11 int n; 12 int a[N]; 13 14 int main() 15 { 16 int n,j=0; 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 19 20 LL maxs = -1e18; //定义一个较小的值,以防有的权值比他还小 21 int depth=0; 22 for(int d=1,i=1;i<=n;d++,i*=2) //表示层数循环 23 { 24 LL s=0; 25 for(j=i;j<i+pow(2,d-1)&&j<=n;j++) //第二个判断条件是以防有的层都不是满的 26 s+=a[j]; 27 if(s>maxs) 28 { 29 maxs=s; 30 depth=d; //记录层数 31 } 32 33 } 34 35 cout<<depth<<endl; 36 37 return 0; 38 }