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

server/2024/12/26 8:01:16/

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

相关文章

最新高性能多目标优化算法:多目标麋鹿优化算法(MOEHO)求解LRMOP1-LRMOP6及工程应用---盘式制动器设计,提供完整MATLAB代码

一、麋鹿优化算法 麋鹿优化算法&#xff08;Elephant Herding Optimization&#xff0c;EHO&#xff09;是2024年提出的一种启发式优化算法&#xff0c;该算法的灵感来源于麋鹿群的繁殖过程&#xff0c;包括发情期和产犊期。在发情期&#xff0c;麋鹿群根据公麋鹿之间的争斗分…

理想很丰满的Ollama-OCR

最近看到不少关于 Ollama OCR 项目友好可用的文章&#xff0c;也来试试。 安装依赖 我的环境是 python 3.11&#xff0c;直接安装下面这个库即可。 pip install ollama-ocr参考&#xff1a;imanoop7/Ollama-OCR 项目介绍 Ollama OCR &#xff1a;一个强大的光学字符识别&am…

Hive SQL 之 `LATERAL VIEW EXPLODE` 的正确打开方式

一文彻底搞懂 LATERAL VIEW EXPLODE 1. 引言 在处理复杂数据结构&#xff08;如数组、映射&#xff09;时&#xff0c;Hive SQL 提供了强大的功能来简化查询和数据分析。其中&#xff0c;LATERAL VIEW 和 EXPLODE 是两个特别有用的关键字&#xff0c;它们可以帮助我们将复杂的…

Linux零基础速成篇一(理论+实操)

前言&#xff1a;本教程适合Linux零基础学习&#xff0c;也适合Linux期末考试的小伙伴&#xff0c;从头到尾理论与实操相结合&#xff0c;让你快速对Linux进行了解和掌握。 一、Linux概述 为什么要学习Linux操作系统&#xff1f; 完全免费-开源 任何用户均可下载使用 安全…

金融数据可视化实现

一、设计题目 金融数据可视化 二、设计目的 使学生掌握用Pandas第三方库数据计算、数据分析的知识与能力。Pandas是专门用于数据分析的库&#xff0c;其提供的read_excel()方法可以方便的读取xlsx格式的文件中的数据到Pandas中的DataFrame中。 DataFrame.plot(kindline)&am…

分布式 IO 模块:赋能造纸业,革新高速纸机主传动

背景介绍 在当今高速发展的造纸行业&#xff0c;每一个生产环节的高效与精准都关乎着企业的竞争力与未来。而高速纸机主传动系统&#xff0c;作为造纸生产线的 “心脏”&#xff0c;其性能的优劣更是重中之重。 痛点分析 高速纸机在运行过程中&#xff0c;主传动需要面对诸多…

scala借阅图书保存记录(三)

BookDAO package org.app package daoimport models.BookModelimport scala.collection.mutable.ListBuffer//图书&#xff0c;数据操作 class BookDAO {//加载图书&#xff0c;从文件中读入def loadBooks(): ListBuffer[BookModel] {val books new ListBuffer[BookModel]()…

SQL 实战:窗口函数的妙用 – 分析排名与分组聚合

在复杂的数据分析和查询场景中&#xff0c;SQL 窗口函数&#xff08;Window Functions&#xff09;是提升性能和代码可读性的重要工具。窗口函数可以轻松实现排名、分组聚合、滑动平均等复杂计算&#xff0c;避免使用嵌套子查询或冗余的多次表扫描。 本文将通过实战案例&#…