P8681 题解

___w · 2023-03-30 16:09:55 · 题解

solution

题意简述

• 给定一个完全二叉树。

• 求同一深度的节点权值之和最大的深度（深度为第二关键字）。

完全二叉树的性质

设深度为 dep，根节点的深度为 1。则有第 dep 层的节点为 2^{dep}，每层开头的节点编号为 2^{dep-1}，末尾的节点编号为 2^{dep}-1（以上结论叶子节点除外）。

题目分析

有了以上的性质，我们不难想到解题思路：可以对序列 a 进行划分层次，即完全二叉树的每一层，再找最大权值之和。

代码

#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;
        }
    }
    if (sum > Max) {//特判叶子节点
        Max = sum;
        ans = dep;
    }
    cout << ans;
    return 0;
}