P4875 满二叉树（基础）

解题思路

第一步，理解题目在做什么。 给出一棵完全二叉树，结点按从上到下、从左到右的顺序编号，每个结点有权值。要把同一深度的结点权值加起来，找出权值之和最大的深度；如果并列，输出较小的深度。

第二步，发现深度的规律。 在按层编号的二叉树里，编号为 i 的结点的深度等于"i 连续除以 2 直到 0 的次数"。比如编号 1 是第 1 层，编号 2、3 是第 2 层，编号 4~7 是第 3 层。第 k 层能放 2^(k-1) 个结点。

第三步，把权值累加到对应深度。 用数组 sum[dep] 保存第 dep 层的权值之和。读入第 i 个权值时，先算出它属于第几层，再累加进去。

第四步，找和最大的层。 从第 1 层开始往下比较，用"严格大于"更新答案：只有当前层和更大才换。这样当两层和一样大时，保留更小的深度，正好满足并列取小。

举个例子。 样例 n=6，权值 1 5 6 1 2 3。第 1 层只有结点 1，和是 1；第 2 层有结点 2、3，和是 5+6=11；第 3 层有结点 4、5、6，和是 1+2+3=6。最大的是第 2 层，输出 2。

边界情况。 n<101，最多 7 层，sum 数组开到 10 足够。权值都是正整数，每层和用 int 存不会溢出。

参考代码

// 完全二叉树按深度求和：结点i的深度=log2(i)+1，比较各层权值和
#include <iostream>
using namespace std;

int sum[10];  // 各深度的权值之和

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int w;
        cin >> w;
        int dep = 0, t = i;
        while (t > 0) { t /= 2; dep++; }  // 求结点i的深度
        sum[dep] += w;
    }
    int ans = 1;
    for (int d = 1; d <= 8; d++)
        if (sum[d] > sum[ans]) ans = d;   // 严格大于，平局取小深度
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度。 每个结点求一次深度，每次循环除以 2，最多 O(log n) 次，n 个结点合计 O(n log n)。n 最大 100，非常快。

空间复杂度。 只用一个长度固定的 sum 数组存每层和，空间复杂度是 O(1)。