树的知识---完全二叉树的权值
作者:
古德古德
,
2022-04-08 09:53:08
,
所有人可见
,
阅读 212
/*思路:对于树,根节点从1开始,层数从1开始 */
//一个k层的树有2^k - 1个节点 ,每一层的节点个数为2^(k-1)个
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +10;
int n;
long long a[N];
int main()
{
cin >> n;
for(int i = 1;i <=n;i++) cin >> a[i];
long long res = -1e18;
int len = 1;
for(int i = 1,d = 1; i<=n ; i = i*2,d++ )
{
long long sum = 0;
for(int j = i; j < i+pow(2,d-1) && j <= n; j++) //每层有2^(d-1)个节点
{
sum += a[j];
}
if(sum > res)
{
res = sum;
len = d;
}
}
cout << len;
return 0;
}