AcWing 1240. 完全二叉树的权值 ( 双指针 O(n) )
原题链接
简单
作者:
北孤_YCL
,
2024-04-09 19:44:34
,
所有人可见
,
阅读 1
#include<iostream>
#define int long long
using namespace std;
const int N = 100010;
int a[N];
int n;
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int pos = 1, maxn = -1e18;
// d表示层数,i表示每一层的起点
for (int d = 1, i = 1; i <= n; d++, i *= 2)
{
int s = 0;
for (int j = i; j < i+ (1 << d - 1) && j <= n; j++) // 遍历每一层,求和 , 每一层的最后一个点是 i+(1<<d-1)
s += a[j];
//更新maxn,位置pos
if (maxn < s)
maxn = s, pos = d;
}
cout << pos << '\n';
return 0;
}