资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从
上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点
权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,
A2, · · · AN 。
输出格式
输出一个整数代表答案。
样例输入
7
1 6 5 4 3 2 1
样例输出
2
评测用例规模与约定
对于所有评测用例，1 ≤ N
≤ 100000，−100000 ≤ Ai ≤ 100000。
#include <iostream> using namespace std; const int N = 1000000; static int A[N]; static int sum[N] = { 0 }; static int Tree[1000][100000] = { 0 }; int main() { long long n; int t = 0; long long k = 1; int i; cin >> n; for (int i = 0; i < n; i++) { cin >> A[i]; } for (i = 0; t < n ; i++) { for (int j = 0; j < k; j++) { Tree[i][j] = A[t++]; } k *= 2;//更新层数 } k = 1; int maxi = 0, mini = 0; for (int l = 0; l < i; l++) { for (int j = 0; j < k; j++) { sum[l] += Tree[l][j]; } if (sum[maxi] < sum[l]) { maxi = l; } if (sum[mini] > sum[l]) { mini = l; } k *= 2; } int num = 0; for (int l = 0; l < i; l++) { if (sum[l] == sum[maxi]) { num++; } } if (num < 2) { cout << maxi + 1; } else cout << mini + 1; return 0; }
