算法分析
层序遍历
由于要计算出哪层的节点权值之和最大,因此采用层序遍历整个序列,因为序列满足完全二叉树的性质,因此可以用二叉堆来模拟,因为根的深度为1,假设序列开始的下标为1,某层的深度为k,那么每层的起始下标就是 $2^{k-1} $,该层对应的长度就是 $2^{k-1}$
当某层的起始下标大于总节点个数时结束
时间复杂度 $O(N)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int INF = 0x3f3f3f3f ;//因为数据的最终答案在INF范围内
int n ;
int main(){
int root = 1,tmp = 1,lev = 1 ;//tmp记录遍历到了第几层,root记录每层的起始下标和长度,lev是要输出的答案
int ans = -INF ;
cin >> n ;
while(root<=n){
LL res = 0 ;//权值之和会爆int
for(int i=root;i<=2*root-1 && i<=n;i++){//下标不能越界,可以边读边做
int a ;
cin >> a ;
res += a ;
}
if(res>ans){
ans = res ;
lev = tmp ;
}
root *= 2 ;
tmp ++ ;
}
cout << lev << endl ;
return 0 ;
}