eclipse tomcat 网站开发,怎么制作网站来赚钱,在线制作图网站,wordpress搭建网盘# [蓝桥杯 2019 省 AB] 完全二叉树的权值
## 题目描述
给定一棵包含 $N$ 个节点的完全二叉树#xff0c;树上每个节点都有一个权值#xff0c;按从上到下、从左到右的顺序依次是 $A_1,A_2, \cdots A_N$#xff0c;如下图所示#xff1a; 现在小明要把相同深度的节点的权值…# [蓝桥杯 2019 省 AB] 完全二叉树的权值
## 题目描述
给定一棵包含 $N$ 个节点的完全二叉树树上每个节点都有一个权值按从上到下、从左到右的顺序依次是 $A_1,A_2, \cdots A_N$如下图所示 现在小明要把相同深度的节点的权值加在一起他想知道哪个深度的节点权值之和最大如果有多个深度的权值和同为最大请你输出其中最小的深度。
注根的深度是 $1$。
## 输入格式
第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1,A_2, \cdots, A_N$。
## 输出格式
输出一个整数代表答案。
## 样例 #1
### 样例输入 #1 7 1 6 5 4 3 2 1
### 样例输出 #1 2
## 提示
对于所有评测用例$1 \le N \le 10^5$$0 \le |A_i| \le 10^5$。
蓝桥杯 2019 省赛 A 组 F 题B 组 G 题。 思路根据题意我们不难发现这道题的节点是按照树的层数进行输入的。而我们又知道对于一个 x 层的完全二叉树其每层的节点数除最后一层外均为 2^n−1其中 n 为层数且从 1 开始。那么我们就可以一边输入一遍查找每次判断一下输入的数是不是这一层的最后一个节点。如果是取最大值如果不是继续输入即可。
#include bits/stdc.h
using namespace std;
int n, a, sum, ans, dep 1, Max -1e9;
int main() {cin n;for (int i 1; i n; i) {cin a;sum a;if (i (1 dep)-1) {//若是末尾节点切换到下一层if (sum Max) {//找到可行解Max sum;ans dep;}dep;sum 0;//每层算完后 重置为0进行下一层的计算}}if (sum Max) {//特判叶子节点Max sum;ans dep;}cout ans;return 0;
}
关于二叉树的性质等等请转移此篇讲的很详细。一次聊个透彻满二叉树、完全二叉树、二叉搜索树二叉平衡树-CSDN博客
