AcWing 1240. 完全二叉树的权值——前缀和做法和Y总方法(更好理解)
原题链接
简单
作者:
普通上班族
,
2023-03-23 11:32:44
,
所有人可见
,
阅读 154
前缀和解法
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<climits> //用于求出long long的最小值
#include<cmath> //求对数
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
LL s[N],sum[N]; //s[i]是前缀和数组 sum[i]是第i层节点之和。
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
int high=(int)(log(n)/log(2))+1; //根据完全二叉树的性质,求出二叉树的高度
LL maxv=LLONG_MIN,depth=0; //初始化最大值和最小深度
for(int i=1;i<=high;i++)
{
int y,x;
y=(1<<i)-1; //等于 y=pow(2,i)-1 位运算左移i位,等于乘以2^i;
x=(1<<(i-1))-1; // 等于 x=pow(2,i-1)-1;
if(x<=n &&y<=n) //未到达最后一层
{
sum[i]=s[y]-s[x];
}
else if(x<=n && y>n) //到达最后一层时,可能出现n<y的情况,这个时候就要用s[n]-s[x],而不能用s[y]-s[x];
{
sum[i]=s[n]-s[x];
}
if(sum[i]>maxv) //找出每层的最大值,并且记录深度
{
maxv=sum[i];
depth=i;
}
}
cout<<depth<<endl;
return 0;
}
Y总解法
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<climits>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int high=(int)(log(n)/log(2))+1; //求出树高
LL maxv=LLONG_MIN,depth=0; //初始化每层的最大值和树的最小深度。 i
//int 的最小值:INT_MIN long long的最小值:LLONG_MIN
for(int i=1;i<=high;i++) //遍历树的高度
{
LL s=0;
//求出树的每一层的和,每一层节点起始范围为[2^(i-1),2^i-1]或者[2^(i-1),n]
for(int j=1<<(i-1);j<=(1<<i)-1&&j<=n;j++)
{
s+=a[j];
}
if(s>maxv)
{
maxv=s;
depth=i;
}
}
cout<<depth<<endl;
return 0;
}