AcWing 1240. 完全二叉树的权值
原题链接
简单
作者:
牛奶小柒Luke
,
2021-04-14 20:12:10
,
所有人可见
,
阅读 225
双指针算法,定义层数跟该层第一个数
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int depth = 0;
LL maxn = -1e9;
for(int i = 1,d = 1;i <= n;i *= 2,++d){
LL s = 0;
for(int j = i;j <= n && j < i + (1 << d - 1);++j) s += a[j];
if(maxn <= s){
maxn = s;
depth = d;
}
}
printf("%d\n",depth);
return 0;
}