蓝桥杯历届题目及解析汇总（附思路及代码）【点击此进入】
蓝桥杯，ACM算法学习【文档】【视频】大放送【点击此进入】
第七题
标题：完全二叉树的权值（时间限制: 1.0s 内存限制: 256.0MB 本题总分：20 分）
【问题描述】 给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A 1 , A 2 , ··· A N ，如下图所示： 现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。 注：根的深度是 1。 【输入格式】 第一行包含一个整数 N。 第二行包含 N 个整数 A 1 , A 2 , ··· A N 。 【输出格式】 输出一个整数代表答案。 【样例输入】 7 1 6 5 4 3 2 1 试题G: 完全二叉树的权值 10 第十届蓝桥杯大赛软件类省赛 C/C++ 大学 B 组 【样例输出】 2 【评测用例规模与约定】 对于所有评测用例，1 ≤ N ≤ 100000，−100000 ≤ A i ≤ 100000。
解题思路：
这题如果了解完全二叉树的特性就不难了，完全二叉树的第 i 层的最大节点数为 2^(i-1) 个，那么对于某个下标的元素，我们只需要知道他属于哪一层就行了，因为给的数据范围为 100000 个节点以内，这么多节点组成的完全二叉树有多少层呢？我们知道完全二叉树的节点总数和深度的关系为深度为 n 的完全二叉树最多拥有 2^n - 1 个节点，也就是当完全二叉树为满二叉树的时候节点数最多。而一颗层数为 17 层的完全二叉树最大节点数为 2^17 - 1 = 131071，已经大于给定的 n 的范围，那么我们计算出每一个节点所属的深度层，再统计就很简单了，因为题目中给的根的深度为 1, 那么我们计算的深度需要往后移一位，即最大深度为 18
代码：
#include <iostream>
#include <cstdio>
using namespace std
;
const int MAX_DEEP
= 18;
long long temp
[MAX_DEEP
+ 1];
int getDeep(int n
) {
int res
= 0;
while (n
> 0) {
n
/= 2;
res
++;
}
return res
;
}
int main() {
int n
, t
;
cin
>> n
;
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &t
);
temp
[getDeep(i
)] += t
;
}
int res
= 0x80000000, resDeep
;
for (int i
= 1; i
<= MAX_DEEP
; i
++) {
if (temp
[i
] > res
) {
res
= temp
[i
];
resDeep
= i
;
}
}
cout
<< resDeep
<< endl
;
return 0;
}
答案：387420489
蓝桥杯，ACM算法进阶资料大放送
