2019年第十届蓝桥杯C/C++ 省赛B组试题G：完全二叉树的权值

Myth丶恋晨 2022-10-19 04:19 17阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70][]

![20210709174328963.png][]

**例子：**

输入：

7
    
    165432

输出：

分析：输入7个数

二叉树为：

6 5

4 3 2 1

用数组sum来计算每个深度的权值和为多少。

每个深度的最后一个数为（2的deep次方-1），根据这个性质进行判断划分深度。

#include<math.h>
    #include<stdio.h>
    int A[100010];
    int max_sum =0; 
    int main()
    {
    	int sum[100010]={0};//计数
    	int N;
    	int i = 1;
    	int deep = 1; //深度起始值
    	int min_deep = 1;
    	scanf("%d",&N);//输入要输入的数量
    	for(;i <= N; ++i)
    	{
    		if(i>pow(2, deep)-1)//划分每个深度界限
    		{
    			deep++;
    		}
    		scanf("%d",&A[i]);
    		sum[deep]+=A[i];//计算和值与下面操作配合
    
    	}
    	for(i=1;i<=deep;i++)
    	{			
    		if(max_sum < sum[i])//不要取等号，因为题目要最小的深度 
    			{     
    				min_deep = i;//置换出最大值的深度
    				max_sum = sum[i];//置换出最大值
    			}
    	}
    	printf("%d",min_deep);
    	return 0;
    }

例子不单单要考虑一个，有可能尽量发散考虑其他的例子，随意输入的例子，进行检验。

#include<math.h>
    #include<stdio.h>
    int A[100010];
    long long max_sum = -100000000000; //最大的和，由于题目的范围是-100000
    int main()
    {
    	int N;
    	int i = 1;
    	int deep = 1; //深度起始值
    	int sum = 0; //每行的和 
    	int min_deep = 1;
    	scanf("%d",&N);//输入要输入的数量
    	for(;i <= N; ++i)
    	{
    		scanf("%d",&A[i]);
    		sum += A[i];//计算和值与下面操作配合
    		if(i == pow(2, deep) - 1)//划分每个深度界限
    		{
    			if(max_sum < sum)//不要取等号，因为题目要最小的深度 
    			{     
    				min_deep = deep;//置换出最大值的深度
    				max_sum = sum;//置换出最大值
    			}
    			sum=0;//计算完每深度和完，重置和。
    			deep++;
    		}
    	}
    	printf("%d",min_deep);
    	return 0;
    }

![20210709174613648.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70]: /images/20221005/3a098a73d15245f885e6dac39f15e9b7.png
[20210709174328963.png]: /images/20221005/ddf23373a3e44c67a6f1e0113fb52017.png
[20210709174613648.png]: /images/20221005/b030f5891f4b49f3bec817914ebd99ea.png