题目描述

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

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

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

注：根的深度是 1。

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。

输出格式
输出一个整数代表答案。

数据范围
1≤N≤105,
−105≤Ai≤105

样例

7
1 6 5 4 3 2 1

2

完全二叉树的性质，加上i, j, k 三个指针，一个for循环完事儿，不过我开了一个cnt数组来存每一层的权值和，Y总的代码没有，也算是用空间换时间吧

C++代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

LL tr[N];
LL cnt[50];

int main()
{
    int n, k = 1;scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) scanf("%lld", &tr[i]);

    for(int i = 1, j = 1; i <= n; ++ i)
    {
        cnt[k] += tr[i];

        if(i - j >= (1 << (k - 1)) - 1)
        {
            j = i + 1;
            k ++;
        }
    }

    int ans = 0, maxx = 1-1e6;
    for(int i = 1; i <= k ; ++ i)
        if(cnt[i] > maxx)
        {
            maxx = cnt[i];
            ans = i;
        }
    cout << ans <<endl;
    return 0;

}