AcWing 1240. 完全二叉树的权值
原题链接
简单
作者:
ofs
,
2024-04-11 23:51:27
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e5+10;
int a[N];
int n;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
//输入权值
for(int i=1;i<=n;i++) //注意下标从1开始
{
cin>>a[i];
}
//maxs是权值和最大的
//把他初始化为一个不可能取到的值
//depth是权值最大时的层深
int maxs=-INF;
int depth=0;
//双指针,d与i
for(int d=1,i=1;i<=n;i*=2,d++) //d是层数代表第几层,i代表第几层开始的下标
{
int s=0;
//看似是两重循环,实则时间复杂度只为o(n)
//因为这个for循环实现的是这一层的权值的加和,相当于每个权值只出现一次
for(int j=i;j<i+(1<<d-1)&&j<=n;j++)//使用位运算(1<<d-1),时间复杂度为O(1),代表2^(d-1)
s+=a[j];
if(s>maxs)
{
maxs=s;
depth=d;
}
}
cout<<depth;
return 0;
}