完全二叉树的权值

一、题目内容

题目描述

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

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入描述

第一行包含一个整数 N（1 ≤ N ≤ 105）。

第二行包含N个整数A1​，A2，⋅⋅⋅ AN​（−10^5 ≤ Ai ​≤ 10^5）。

输出描述

输出一个整数代表答案。

输入输出样例

输入

71 6 5 4 3 2 1

输出

2

运行限制

  • 最大运行时间：1s
  • 最大运行内存：256M

二、思路分析

题目给的是完全二叉树，而对于完全二叉树，第一层有1个结点，第2层2个，第3层4个，… ，第i层 个；那么倒过来想，第k个数在第层（ceil()函数表示向上取整）。

三、代码实现

#include using namespace std;int sum[100000];int main() {int n;cin >> n;for (int i = 1; i > a;int d = ceil(log(i + 1) / log(2)); //计算节点i的深度sum[d] += a; //各个深度的结点累加求和}int maxx = 0;int ans;for (int i = 1; i  maxx) {maxx = sum[i]; //更新最大权值和ans = i; //更新深度}}cout << ans << endl;return 0;}

加油哦！ 如有错误和需要改进完善之处，欢迎大家纠正指教。