AcWing 1240. 完全二叉树的权值——模拟枚举题
原题链接
简单
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n;
int a[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
LL maxs = -1e18;
int idx = 0;//记录最终答案——层数
//枚举每一层depth,枚举每一层对应地起点i
for(int depth = 1, i = 1; i <= n; i *= 2, depth ++)
{
LL sum = 0;
//枚举在第depth层时,从起点i遍历到第depth层的终点
//当第depth层是满的时候,终点是“i + (1 << depth - 1) - 1”
//当不满的时候,即第depth层是最后一层,终点是n
//其中,(1 << depth - 1)求的是第depth层的结点数量。
//“i + (1 << depth - 1)”求的是第depth + 1层的起点
for(int j = i; j < i + (1 << depth - 1) && j <= n; j ++)
{
sum += a[j];
}
if(sum > maxs)
{
idx = depth;
maxs = sum;
}
}
cout << idx << endl;
return 0;
}