AcWing 1240. 完全二叉树的权值
原题链接
简单
作者:
sy123
,
2020-12-22 22:26:37
,
所有人可见
,
阅读 364
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;//可能爆出int
const int N = 100010;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
LL maxs = -1e18;
int depth = 0;
for (int d = 1, i = 1; i <= n; i *= 2, d ++ )//d是层数,i是每层开头的下标
{
LL s = 0;
for (int j = i; j <= i + i - 1 && j <= n; j ++ )//i + i - 1每层多少数
s += a[j];
if (s > maxs)
{
maxs = s;
depth = d;
}
}
printf("%d\n", depth);
return 0;
}