[题目概述]
给定一棵包含 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总的这个代码就很简洁。
- 别忘了点赞关注加收藏!