完全二叉树的权值(蓝桥杯2019年试题G)

devtools/2024/12/22 23:56:29/

       给定一棵包含N个节点的完全二叉树,树上的每个节点都有一个权值,按从上到小、从左到右的顺序依次是A1、A2……An,(1,2,n为下标。)如下图所示。

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

      注意:根的深度是1。

     【输入格式】

       第一行包含一个整数N。

       第二行包含N个整数A1,A2,……An。  (1,2,n为下标。)

    【输出格式】

     输出一个整数,代表答案

    【样例输入】

      7

      1   6     5   4    3    2    1

    【样例输出】

      2

     【评测用例规模与约定】

       对于所有评测用例, N >= 1 && N <= 100000,   Ai(i为下标)>=-100000&&<=100000。

     【解析】

        本题并无特殊技巧,对每一层进行遍历并算出每层的权值,最后比较出最大值即可。需要注意二叉树的存储和数组下标的关系,以给出的数据为例。

        数据的存储为

下标i1234567
Ai(i为下村)1654321

        二叉树的形式为

          根据上图可以得出以下结论。

     (1)每层第一个元素的下标为2^(n-1),最后一个元素的下标是2^n-1。

     (2)若元素的节点下标为i,则其所在的层数为log2i。(2为下标)

     【参考程序如下】

#include <iostream>
#include <math.h>
using namespace std;
const int N = 10010;
long long a[N],maxsize = -0x3f3f3f3;      //初始为负无穷大 int main(int argc, char** argv) {int n;cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];       // a数组存储的是每个节点的权值int res;for(int i = 1; i <= n; i *= 2){long long s = 0;for(int j = i; j <= i * 2 - 1 && j <= n;j++){s += a[j];}if(s > maxsize){maxsize = s;res = (int) log2(i) + 1;}} cout << res;return 0;
}

【运行结果如下】


http://www.ppmy.cn/devtools/144515.html

相关文章

uniapp Native.js 调用安卓arr原生service

有问题&#xff0c;文中的内容不正确 最近搞了个uni小项目&#xff0c;一个定制的小平板&#xff0c;带一个nfc设备&#xff0c;厂家只给了一套安卓原生demo&#xff0c;头一次玩原生安卓&#xff0c;废了好半天劲打出来arr包&#xff0c;想镶进uniapp里&#xff0c;网上查了好…

Qt WORD/PDF(四)使用 QAxObject 对 Word 替换(QWidget)

关于QT Widget 其它文章请点击这里: QT Widget 国际站点 GitHub: https://github.com/chenchuhan 国内站点 Gitee : https://gitee.com/chuck_chee 姊妹篇: Qt WORD/PDF&#xff08;一&#xff09;使用 QtPdfium库实现 PDF 操作 Qt WORD/PDF&#xff08;二…

Mac配置 Node镜像源的时候报错解决办法

在Mac电脑中配置国内镜像源的时候报错,提示权限问题,无法写入配置文件。本文提供解决方法,青测有效。 一、原因分析 遇到的错误是由于 .npm 目录下的文件被 root 用户所拥有,导致当前用户无法写入相关配置文件。 二、解决办法 在终端输入以下命令,输入管理员密码即可。 su…

Linux逻辑卷动态扩容

Linux逻辑卷动态扩容 一、查看当前文件系统磁盘空间情况二、将新磁盘初始化为物理卷三、将新的物理卷归到需要扩容的卷组当中四、将卷组中的空间分配到具体的逻辑卷上五、逻辑卷扩容完成后&#xff0c;需要动态调整才能使用新分配的空间。 一、查看当前文件系统磁盘空间情况 使…

在 Spark 上实现 Graph Embedding

在 Spark 上实现 Graph Embedding 主要涉及利用大规模图数据来训练模型&#xff0c;以学习节点的低维表示&#xff08;嵌入&#xff09;。这些嵌入能够捕捉和反映图中的节点间关系&#xff0c;如社交网络的朋友关系或者物品之间的相似性。在 Spark 上进行这一任务&#xff0c;可…

C++点云大文件读取

C点云大文件读取 1. 常规读取1.1 逐行读取1.2 逐字节读取 2. 并行读取 (Multithreading)3. 使用缓冲读取 (Buffered I/O)4. 内存映射文件 (Memory Mapping) 在C中读取大文件时&#xff0c;如果需要提高读取速度&#xff0c;可以考虑以下几种方法&#xff1a; 1. 常规读取 常规…

日拱一卒(19)——leetcode学习记录:两个子序列的最大点积

一、题目 给你两个数组 nums1 和 nums2 。 请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。 数组的非空子序列是通过删除原数组中某些元素&#xff08;可能一个也不删除&#xff09;后剩余数字组成的序列&#xff0c;但不能改变数字间相对顺序。比方说&a…

在 Unity 6 中使用APV为您的世界创建全局照明的新方法(一)

Unity 6 中推出的新照明功能让您能够更快速、更高效的完成对烘焙场景的照明工作&#xff0c;在本文中我们将与大家详细分享在 Unity 6 中应用自适应探针卷创建快速全局光照的更多细节与具体应用方法。由于内容比较丰富&#xff0c;我们将把内容分为三篇文章&#xff0c;以便大家…