p8681

Yashajin_Ai · 2023-03-30 14:55:14 · 题解

前置芝士：

先看一看完全二叉树概念：

完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1\sim h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

正片

我们的目标是看懂这题涉及的完全二叉树的方面，那么——此题明显是涉及完全二叉树结点数和层数的关系。

所以分两种情况求解：

满二叉树 \log _{2}\left( n+1\right) 为他的深度，完全二叉树 \left( \log _{2}n\right) +1 为他的深度。

#include<bits/stdc++.h>
using namespace std;
int a[100001],n,m,ans,maxn=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        int d=log(2*i)/log(2);//手动转log以2为底数的深度
        a[d]+=m;
    }
    for(int i=1;i<=n;i++){
        if(a[i]>maxn){//寻找哪个深度的节点权值之和最大
            maxn=a[i];
            ans=i;
        }
    }
    cout<<ans;
    return 0;
}