[题目概述]
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 A 1 , A 2 , ⋅ ⋅ ⋅ A N A_1,A_2,⋅⋅⋅A_N A1,A2,⋅⋅⋅AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?
如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。
输出格式
输出一个整数代表答案。
数据范围
1 ≤ N ≤ 1 0 5 1 ≤ N ≤ 10^5 1≤N≤105,
− 1 0 5 ≤ A i ≤ 1 0 5 −10^5 ≤ A_i ≤ 10^5 −105≤Ai≤105
输入样例:
7
1 6 5 4 3 2 1
输出样例:
2
题目意思很清楚,就是让求哪一层的值之和最大。那么我们计算的时候两个问题就是当前在哪一层,每层由哪个数开始,这也就构成了双指针思想的两个指针。一个是层数,一个是本层从哪个数开始。
- 完整代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>using namespace std;const int N = 100005;
int f[N], n;
int main() {cin >> n;for (int i = 1; i <= n; i ++)cin >> f[i];int depth = 0;// 将maxs值定义为最小值long long maxs = -1e18;for (int d = 1, i = 1; i <= n; d ++, i *= 2) {long long sum = 0;// 左移就是2的多少次方,i + (1 << d - 1)是每层的结点数for (int j = i; j < i + (1 << d - 1) && j <= n; j ++) {sum += f[j];}if (sum > maxs) {maxs = sum;depth = d;}}cout << depth;return 0;
}
- 本题的分享就结束了,虽然题很简单,但我花费了好长时间做出来的方法还是很笨,y总的这个代码就很简洁。
- 别忘了点赞关注加收藏!