题目描述
给定一棵包含$N$个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是$A_1,A_2,…,A_N$。现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。
样例
输入格式
7
1 6 5 4 3 2 1
输出格式
2
算法
算法思想(前缀和)
- 因为涉及到
区间求和
因此想到前缀和
思想; - 通过前缀和进行预处理,便于后续得到某一深度的节点权值之和;
- 由于完全二叉树可以用一维数组来存,因此可根据完全二叉树所对应的一维数组的下标特征来进行求解某一深度节点权值之和;
- 根据完全二叉树的特征可知,令某一深度的第一个节点坐标为$i$,易知该深度的最后一个节点的下标可能为$n$或者为$i - 1 + 2^{log_2(i)}$。之所以可能为$n$,是因为完全二叉树不一定是满二叉树,需要考虑此种情况;
- 基于上述算法思想可求解答案。
时间复杂度
- 时间复杂度为O(n)
C++ 代码
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N];
LL sum[N];
int flag;
LL res = -N;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i]; //前缀和预处理
}
for (int i = 1; i <= n; i = 2 * i)
{
int t = pow(2, log2(i));
if (i + t - 1 <= n)
{
if (sum[i + t - 1] - sum[i - 1] > res) //与当前最大的深度权值之和进行比较
{
res = sum[i - 1 + t] - sum[i - 1];
flag = log2(i) + 1; //用于记录深度
}
}
else
{
if(sum[n] - sum[i - 1] > res) //与当前最大的深度权值之和进行比较
{
res = sum[n] - sum[i - 1];
flag = log2(i) + 1; //用于记录深度
}
}
}
cout << flag << endl;
return 0;
}
易错点
- 由于$A_i$的值可能取负数,因此最大的
深度节点权值之和
很可能也是负数。因此要将$res$的值初始化为$-N$,否则最后一个测试用例过不了。 - 另一个易错点是需要将
前缀和数组
和res
的数据类型设置为long long
,因为通过对数据范围的计算,最大情况会超过$2*10^9$,会爆$int$,因此需要用long long
。