蓝桥杯--完全二叉树的权值

本文主要是介绍蓝桥杯--完全二叉树的权值，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

今天又学会了一个题，想和大家分享一下

题目见下：

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1, A2, ··· AN如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入描述

第一行包含一个整数 N（1N 0^5）N（1≤N≤105）。

第二行包含 NN 个整数 A_1, A_2, ··· A_N （1≤N≤105）

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

7
1 6 5 4 3 2 1

2

此题可用队列知识来解决，但是此题很多细节，千万要小心！！！

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const ll num=-1e10; 
//有负数这要max的初始化的值要小心啊！！！
且小心int会爆！！！ 
queue<int>que;
int main(){
	int n,x;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x;
		que.push(x);
	}
	//一级一级的区间有[2^(n-1),2^n-1]
	int maxi=0,cnt=1;
	ll sum=0,max=num,b=2;
	for(int i=1;que.size();i++){
		sum+=que.front();
		que.pop() ;
		if(i==b-1){//注意最后一层,不一定是满的 
			if(sum>max){
			max=sum;
			maxi=cnt;
			}
			cnt++;
			b*=2;
			sum=0;
		}
	} 
	if(sum>max){
		maxi=cnt;
	}
	cout<<maxi<<endl;
	return 0;
} 

这篇关于蓝桥杯--完全二叉树的权值的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！