自动搬运

查看原文

来自洛谷，原作者为

	___w **

搬运于2025-08-24 22:41:25，当前版本为作者最后更新于2023-03-30 16:09:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

solution

题意简述

• 给定一个完全二叉树。

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

• $1≤N≤10^5$，$0 \le |A_i| \le 10^5$。

完全二叉树的性质

设深度为 $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;
}