蓝桥杯2019年第十届真题——完全二叉树的权值

完全二叉树的权值

---

一、题目内容

题目描述

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入描述

第一行包含一个整数 N（1 ≤ N ≤ 105）。

第二行包含 N 个整数A1，A2，⋅⋅⋅  AN（−10^5 ≤ Ai ≤ 10^5）。

输出描述

输出一个整数代表答案。

输入输出样例

输入

1.  
   7
2.  
   1 6 5 4 3 2 1

输出 

2

运行限制

• 最大运行时间：1s
• 最大运行内存：256M

---

二、思路分析

        题目给的是完全二叉树，而对于完全二叉树，第一层有 1 个结点，第 2 层 2 个，第 3 层 4 个，…  ，第 i 层  个；那么倒过来想，第 k 个数在第层（ceil()函数表示向上取整）。

---

三、代码实现

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
    
4.  
   int sum[100000];
5.  
    
6.  
   int main() {
7.  
   int n;
8.  
   cin >> n;
9.  
   for (int i = 1; i <= n; i ) {
10.  
    int a;
11.  
    cin >> a;
12.  
    int d = ceil(log(i 1) / log(2)); //计算节点i的深度
13.  
    sum[d] = a; //各个深度的结点累加求和
14.  
    }
15.  
    int maxx = 0;
16.  
    int ans;
17.  
    for (int i = 1; i <= 100000; i ) {
18.  
    if (sum[i] > maxx) {
19.  
    maxx = sum[i]; //更新最大权值和
20.  
    ans = i; //更新深度
21.  
    }
22.  
    }
23.  
    cout << ans << endl;
24.  
     
25.  
    return 0;
26.  
    }

加油哦！ 如有错误和需要改进完善之处，欢迎大家纠正指教。

这篇好文章是转载于：学新通技术网