本文最后更新于：19 分钟前
[蓝桥杯 2019 省 AB] 完全二叉树的权值
题目描述
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,…An，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是1。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…An。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
样例输出 #1
提示
对于所有评测用例，1<=n<=1e5，0<=|Ai|<=1e5。
理解
注意到图中左边，1，2，4，都是二的倍数，每一次循环从每一层从左往右加，找出最大的并保存。
代码
60分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int n;
const int N=1e5+10;
int arr[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
int root=1,res=1;
long long MAX=arr[1];
for(int i=2;i<=n;)
{
int t=i;
long long sum=0;
root++;
while(i<2*t)
{
sum+=arr[i];
i++;
}
if(MAX<=sum)
{
MAX=sum;
res=root;
}
}
cout<<res<<endl;
return 0;
}
|
优化
想到用前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
int main(void)
{
int n; cin>>n;
ll max=-9999999,max_d=0;
for(int i=0,length=1,depth=1;i<n;depth++,length*=2)
{
ll s=0;
for(int j=0;j<length&&i<n;j++,i++)
{
int x;
cin>>x;
s+=x;
}
if(s>max)
{
max=s;
max_d=depth;
}
}
cout<<max_d<<endl;
return 0;
}
|