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

embedded/2024/12/26 1:06:54/

       给定一棵包含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/embedded/148758.html

相关文章

uniapp小程序使用webview 嵌套 vue 项目

uniapp小程序使用webview 嵌套 vue 项目 小程序中发送 <web-view :src"urlSrc" message"handleMessage"></web-view>export default {data() {return {urlSrc: "",};},onLoad(options) {// 我需要的参数比较多 所以比较臃肿// 获取…

ROSboard:为您的机器人提供强大的Web可视化工具

ROSboard&#xff1a;为您的机器人提供强大的Web可视化工具 rosboard ROS node that turns your robot into a web server to visualize ROS topics [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/ro/rosboard 项目介绍 ROSboard 是一个专为机器人设计的 Web 服…

【C++基础】09、结构体

一、结构体(struct) C/C 数组允许定义可存储相同类型数据项的变量&#xff0c;但是结构体是 C 中另一种用户自定义的可用的数据类型&#xff0c;它允许存储不同类型的数据项。 结构体用于表示一条记录&#xff0c;假设现在想要跟踪图书馆中书本的动态&#xff0c;可能需要跟踪每…

AIDD - 人工智能药物设计 - 在 Docker 上创建和运行 PostgreSQL + RDKit 卡带环境

在 Docker 上创建和运行 PostgreSQL RDKit 卡带环境 背景 我们将讨论化学数据库。 看起来&#xff0c;如果你在 PostgreSQL 中放置一个 RDKit cartridge &#xff08;扩展&#xff09;&#xff0c;就可以基于 SQL 进行结构相似性搜索&#xff0c;看起来很有趣。但是我找不到…

【故障处理系列--gitlab的CI流水线下载安装包提示报错】

故障现象&#xff1a; 前端同事一直向我反映使用alpine-node系列的镜像&#xff0c;安装包报错故障原因 在CI文件上配置的代理没有生效&#xff0c;导致流水线无法在gitlab-runner上拉取https://registry.npmmirror.com仓库软件包 后来查资料提示说&#xff0c;在gitlab的CI文…

JMeter 二次开发之环境准备

通过JMeter二次开发&#xff0c;可以充分发挥JMeter的潜力&#xff0c;定制化和扩展工具的能力以满足具体需求。无论是开发自定义插件、函数二次开发还是定制UI&#xff0c;深入学习和掌握JMeter的二次开发技术&#xff0c;将为接口功能测试/接口性能测试工作带来更多的便利和效…

Python中所有子图标签Legend显示详解

在数据可视化中&#xff0c;图例&#xff08;legend&#xff09;是一个非常重要的元素&#xff0c;它能够帮助读者理解图表中不同元素的含义。特别是在使用Python进行可视化时&#xff0c;matplotlib库是一个非常强大的工具&#xff0c;能够轻松创建包含多个子图的图表&#xf…

MVCC了解

MVCC&#xff08;多版本并发控制&#xff09;学习指南及代码示例 一、学习MVCC前先了解什么 1. MVCC的定义和作用 MVCC是一种并发控制机制&#xff0c;用于解决并发事务访问数据库时可能出现的问题&#xff0c;如脏读、不可重复读和幻读。它通过为每个数据行维护多个版本来实…