第十届蓝桥试题G:完全二叉树的权值

傷城~ 2022-11-17 05:52 15阅读 0赞

# 完全二叉树的权值 #

给定一棵包含N 个节点的完全二叉树，树上每个节点都有一个权值，按从  
上到下、从左到右的顺序依次是A1, A2, AN，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzUxMTE5MA_size_16_color_FFFFFF_t_70_pic_center]  
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。  
注：根的深度是1。

输入  
第一行包含一个整数N。  
第二行包含N 个整数A1, A2, AN  
对于所有评测用例，1<=N<=100000, -100000<=Ai<=100000。

输出  
输出一个整数代表答案。

#include <stdio.h>
    #include <math.h>
    int a[100005]={ 0};
    int main()
    { 
    	int n,deep=0,max=-1000,t=0;//deep表示输出的最小深度 t表示最大深度 
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{ 
    		scanf("%d",&a[i]);
    	}
    	for(int i=0;i<10000;i++)//用来计算最大深度 
    	{ 
    		if(n==pow(2,i))
    		{ 
    			t=i;
    			break;
    		}
    		if(n<pow(2,i))
    		{ 
    			t=i-1;
    			break;
    		}
    	}
    	int j=1;
    	for(int i=1;i<=t+1;i=pow(2,j-1)) // 根据完全二叉树的性质 深度为i最多有2的i次方-1个结点 最少有2的i个结点 所以一层第一个节点位置是2的i次方 
    	{ 
    		int demp=0,time1=0;
    		time1 = pow(2,j-1);// 完全二叉树 一层最多有2的i-1次方个 节点 time1表示这层的结点数 
    		if(time1>n)
    		{ 
    			time1=n%(time1/2);//万一最后一行不是满的 看最后一行多了几个结点 
    		}
    		while(time1)
    		{ 
    			demp+=a[i+time1-1];
    			time1--;
    		}
    		if(demp>max)
    		{ 
    			max=demp; 
    			deep=j;
    		}
    		j++;//表示当前深度 
    	}
    	printf("%d",deep);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzUxMTE5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/51c349f80c7d4daea71a3a0a16f61e9c.png