2019年第十届蓝桥杯省赛-G.完全二叉树的权值

2022-03-23 · 108次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #树

原题链接

题面

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

二叉树表示

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

注：根的深度是 1。

输入描述

第一行包含一个整数 N（ $1 \leq N \leq 10^5$ ）。

第二行包含 N 个整数 $A_1, A_2, ··· A_N$ （ $−10^5 \leq A_i \leq 10^5$ ）。

输出描述

输出一个整数代表答案。

输入样例

7
1 6 5 4 3 2 1

输出样例

题解

二叉树

由于题目中的节点是按照二叉树的层序遍历给出的，则第一层有 1 个，第二层有 2 个，第三层有 4 个……依次往后统计每层的权值和，最后再进行比较找到最大的即可。

代码

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
int n;
LL s[20];

int main() {
    cin >> n;
    for (int i = 1, d = 1, p = 1, x, j = 0; i <= n; ++i) {
        cin >> x;
        s[d] += x;
        if (++j == p) {
            p *= 2;
            j = 0;
            d++;
        }
    }

    LL maxv = -1e11;
    int ans = 1;
    for (int i = 1; i < 20; i++) {
        if (s[i] > maxv) {
            ans = i;
            maxv = s[i];
        }
    }
    cout << ans << endl;

    return 0;
}

标题：	2019年第十届蓝桥杯省赛-G.完全二叉树的权值
链接：	https://www.fightingok.cn/detail/217
更新：	2022-09-18 22:49:07
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可