日志统计
一、题目内容
题目描述
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。
输入描述
第一行包含一个整数 N(1 ≤ N ≤ 105)。
第二行包含 N 个整数A1,A2,⋅⋅⋅ AN(−10^5 ≤ Ai ≤ 10^5)。
输出描述
输出一个整数代表答案。
输入输出样例
输入
7
1 6 5 4 3 2 1
输出
2
运行限制
- 最大运行时间:1s
- 最大运行内存:256M
二、思路分析
题目给的是完全二叉树,而对于完全二叉树,第一层有 1 个结点,第 2 层 2 个,第 3 层 4 个,… ,第 i 层 个;那么倒过来想,第 k 个数在第层(ceil()函数表示向上取整)。
三、代码实现
#include <bits/stdc++.h>
using namespace std;
int sum[100000];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
int d = ceil(log(i + 1) / log(2)); //计算节点i的深度
sum[d] += a; //各个深度的结点累加求和
}
int maxx = 0;
int ans;
for (int i = 1; i <= 100000; i++) {
if (sum[i] > maxx) {
maxx = sum[i]; //更新最大权值和
ans = i; //更新深度
}
}
cout << ans << endl;
return 0;
}
加油哦! 如有错误和需要改进完善之处,欢迎大家纠正指教。