题目描述

关系

内容

给定一棵包含 $N$ 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 $A_1,A_2,···A_N$，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 $1$。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,···A_N$。

输出格式

输出一个整数代表答案。

数据范围

$1\le N\le {10}^5$,
$-{10}^5\le A_i\le {10}^5$

输入样例：

7
1 6 5 4 3 2 1

输出样例：

2

问题分析

最初思路

对于一个节点的小标 i，那么其子节点的下标为 ${\displaystyle 2\ast i,2\ast i+1}$。如果总共有 n 个节点，那么其深度为 ${\displaystyle \lceil {\log }_{2}n\rceil }$.

如果一个节点的下标为 i，那么其所在的层数为 ${\displaystyle \lfloor {\log }_{2}i+1\rfloor }$.

思路分析

执行流程设计

1. 遍历数组，得出数组 sum，sum[k] 表示层数 k 的和；
2. 最后得出最大的 sum 即可；

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n;
ll sum[N];

int main()
{
    scanf("%d", &n);
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int a, k;
        scanf("%d", &a);
        k = log2(i) + 1;
        sum[k] += a;
    }
    
    int k = 1;
    for (int i = 1; i <= log2(n) + 1; i++) {
        if (ans < sum[i]) {
            k = i;
            ans = sum[i];
        }
    }
    printf("%d", k);
    return 0;
}