当前位置: 首页 > news >正文

[蓝桥杯 2019 省赛 AB] 完全二叉树的权值

# [蓝桥杯 2019 省 AB] 完全二叉树的权值

## 题目描述

给定一棵包含 $N$ 个节点的完全二叉树,树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是 $A_1,A_2, \cdots A_N$,如下图所示:

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

注:根的深度是 $1$。

## 输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2, \cdots, A_N$。

## 输出格式

输出一个整数代表答案。

## 样例 #1

### 样例输入 #1

```
7
1 6 5 4 3 2 1
```

### 样例输出 #1

```
2
```

## 提示

对于所有评测用例,$1 \le N \le 10^5$,$0 \le |A_i| \le 10^5$。

蓝桥杯 2019 省赛 A 组 F 题(B 组 G 题)。

思路:根据题意,我们不难发现:这道题的节点是按照树的层数进行输入的。而我们又知道,对于一个 x 层的完全二叉树,其每层的节点数除最后一层外均为 2^n−1,其中 n 为层数,且从 1 开始。那么,我们就可以一边输入一遍查找,每次判断一下输入的数是不是这一层的最后一个节点。如果是,取最大值;如果不是,继续输入即可。

#include <bits/stdc++.h>
using namespace std;
int n, a, sum, ans, dep = 1, Max = -1e9;
int main() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a;sum += a;if (i == (1 << dep)-1) {//若是末尾节点,切换到下一层if (sum > Max) {//找到可行解Max = sum;ans = dep;}++dep;sum = 0;//每层算完后 重置为0进行下一层的计算}}if (sum > Max) {//特判叶子节点Max = sum;ans = dep;}cout << ans;return 0;
}

关于二叉树的性质等等,请转移此篇,讲的很详细。一次聊个透彻:满二叉树、完全二叉树、二叉搜索树,二叉平衡树-CSDN博客

相关文章:

[蓝桥杯 2019 省赛 AB] 完全二叉树的权值

# [蓝桥杯 2019 省 AB] 完全二叉树的权值 ## 题目描述 给定一棵包含 $N$ 个节点的完全二叉树&#xff0c;树上每个节点都有一个权值&#xff0c;按从上到下、从左到右的顺序依次是 $A_1,A_2, \cdots A_N$&#xff0c;如下图所示&#xff1a; 现在小明要把相同深度的节点的权值…...

亮数据Bright Data,引领高效数据采集新体验

随着互联网和大数据的日益普及&#xff0c;我们对于高速、安全和无限畅通的网络体验追求越发迫切&#xff0c;随之而来的网络安全和隐私保护变得越来越重要。IP代理作为一种实用的代理工具&#xff0c;可以高效地帮我们实现网络数据采集&#xff0c;有效解决网络安全问题&#…...

C#学习笔记

一、事件派发器 在C#中&#xff0c;事件派发器通常是指事件委托和事件处理程序的组合&#xff0c;用于实现一种观察者设计模式。它允许对象在状态发生变化时通知其他对象&#xff0c;从而实现对象之间的解耦。 事件派发器的基本组成部分&#xff1a; 事件委托&#xff08;Ev…...

【A-006】基于SSH的新闻发布系统(含论文)

【A-006】基于SSH的新闻发布系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Jdk7(8)Tomcat7(8)MySQLIntelliJ IDEA(Eclipse) 数据库&#xff1a; MySQL 技术&#xff1a; SpringStruts2HiberanteJSPJquery 适用于&#xff1a; 课程设计&#xff0c;毕业设计&…...

c语言-static

static作用&#xff1a;修饰变量和函数 修饰局部变量-静态局部变量 static未修饰局部变量 #include <stdio.h>void print() {int a 0;a;printf("%d ", a); }int main() {int i 0;for (i 0; i < 10; i){print();}return 0; }运行结果 static修饰局部变…...

zuul的性能调优

文章目录 zuul的性能调优Zuul参数剖析semaphore(信号量)ribbonhystrix高并发下常见Zuul异常熔断 zuul 1.x 与2.x的区别与总结 zuul的性能调优 在项目实践中&#xff0c;使用jemeter多线程并发访问微服务中的接口时候&#xff0c;在Zuul层出现异常、超时等&#xff0c;从而导致整…...

C++中的动态内存管理

1.C中动态内存管理 C语言内存管理方式在C中可以继续使用&#xff0c;但有些地方就无能为力&#xff0c;而且使用起来比较麻烦&#xff0c;因此C又提出了自己的内存管理方式&#xff1a;通过new和delete操作符进行动态内存管理。 1.1 new/delete操作内置类型 c语言和c的动态内存…...

es6的核心语法

在学习低代码时&#xff0c;经常有粉丝会问&#xff0c;低代码需要什么基础&#xff0c;es6就是基础中的一项。我们本篇是做一个扫盲&#xff0c;可以让你对基础有一个概要性的了解&#xff0c;具体的每个知识点可以深入进行了解&#xff0c;再结合官方模板就会有一个不错的掌握…...

Unity | 射线检测及EventSystem总结

目录 一、知识概述 1.Input.mousePosition 2.Camera.ScreenToWorldPoint 3.Camera.ScreenPointToRay 4.Physics2D.Raycast 二、射线相关 1.3D&#xff08;包括UI&#xff09;、射线与ScreenPointToRay 2.3D&#xff08;包括UI&#xff09;、射线与ScreenToWorldPoint …...

职业经验 2024 年测试求职手册

原贴地址: 2024 年测试求职手册 TesterHome 经历年前年后差不多 2 个月左右时候的求职&#xff0c;是时候总结复盘一下了&#xff0c;本打算在自己有着落再复盘&#xff0c;但是一想那时候似乎价值就没现在去做显得有意义一些&#xff0c;这篇帖子更多的是让大家看下有没有心…...

Spring Boot与Redis深度整合:实战指南

Spring Boot 整合 Redis 相当简单&#xff0c;它利用了 Spring Data Redis 项目&#xff0c;使得我们可以在 Spring Boot 应用中轻松地操作 Redis。以下是如何整合 Redis 到 Spring Boot 应用的基本步骤&#xff1a; 1. 添加依赖 首先&#xff0c;在你的 pom.xml 文件中添加 …...

微服务(基础篇-006-Docker安装-CentOS7)

目录 05-初识Docker-Docker的安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p46&spm_id_frompageDriver&vd_source60a35a11f813c6dff0b76089e5e138cc 0.安装Docker 1.CentOS安装Docker 1.1.卸载&#xff08;可选&#xff09; 1.2.安装dock…...

前端-css-01

1.CSS 长度单位和颜色设置 1.1CSS 中的长度单位 px 像素 em 字体大小的倍数&#xff08;字体默认是16px&#xff09; % 百分比 1.2CSS 中的颜色设置方式 1.2.1使用颜色名表示颜色 red、orange、yellow、green、cyan、blue、purple、pink、deeppink、skyblue、greenyellow .…...

Java学习36-Java 多线程安全:懒汉式和饿汉式

JAVA种有两种保证线程安全的方式&#xff0c;分别叫懒汉式Lazy Initialization和饿汉式Eager Initialization&#xff0c;以下是他们的区别&#xff1a; 线程安全性&#xff1a; 懒汉式本身是非线程安全的&#xff0c;因为多个线程可能同时检查实例是否为null&#xff0c;并尝…...

sql常用之CASE WHEN THEN

sql常用之CASE WHEN THEN SQL中的 CASE 类似编程语言里的 if-then-else 语句&#xff0c;用做逻辑判断。可以用于SELECT语句中&#xff0c;也可以用在WHERE&#xff0c;GROUP BY 和 ORDER BY 子句&#xff1b;可以单独使用&#xff0c;也可以和聚合函数结合使用。 语法&#…...

【PduR路由】IPduM模块详细介绍

目录 1.IpduM功能简介 2.IpduM模块依赖的其他模块 2.1RTE (BSW Scheduler) 2.2PDU Router 2.3COM 3.IpduM功能详解 3.1 功能概述 3.2 I-PDU多路复用I-PDU Multiplexing 3.2.1 Definitions and Layout 3.2.2通用功能描述 General 3.2.3模块初始化 Initialization 3.…...

【MySQL】6.MySQL主从复制和读写分离

主从复制 主从复制与读写分离 通常数据库的读/写都在同一个数据库服务器中进行&#xff1b; 但这样在安全性、高可用性和高并发等各个方面无法满足生产环境的实际需求&#xff1b; 因此&#xff0c;通过主从复制的方式同步数据&#xff0c;再通过读写分离提升数据库的并发负载…...

Lucene及概念介绍

Lucene及概念介绍 基础概念倒排索引索引合并分析查询语句的构成 基础概念 Document&#xff1a;我们一次查询或更新的载体&#xff0c;对比于实体类 Field&#xff1a;字段&#xff0c;是key-value格式的数据&#xff0c;对比实体类的字段 Item&#xff1a;一个单词&#xff0…...

密码算法概论

基本概念 什么是密码学&#xff1f; 简单来说&#xff0c;密码学就是研究编制密码和破译密码的技术科学 例题&#xff1a; 密码学的三个阶段 古代到1949年&#xff1a;具有艺术性的科学1949到1975年&#xff1a;IBM制定了加密标准DES1976至今&#xff1a;1976年开创了公钥密…...

实时数仓之实时数仓架构(Hudi)

目前比较流行的实时数仓架构有两类&#xff0c;其中一类是以FlinkDoris为核心的实时数仓架构方案&#xff1b;另一类是以湖仓一体架构为核心的实时数仓架构方案。本文针对FlinkHudi湖仓一体架构进行介绍&#xff0c;这套架构的特点是可以基于一套数据完全实现Lambda架构。实时数…...

保姆级教程:用Coze零代码打造一个能聊天的微信公众号机器人(附服务器配置避坑指南)

零基础玩转Coze&#xff1a;从智能体创建到微信公众号部署全指南 在数字化营销日益重要的今天&#xff0c;拥有一个能24小时响应客户需求的智能客服已成为许多企业的标配。但对于没有技术背景的运营和市场人员来说&#xff0c;开发一个功能完善的聊天机器人似乎遥不可及。Coze平…...

如何用stressapptest进行高效内存和磁盘压力测试?实战案例分享

如何用stressapptest进行高效内存和磁盘压力测试&#xff1f;实战案例分享 在服务器运维和硬件性能评估中&#xff0c;内存和磁盘的稳定性直接关系到系统的可靠性。想象一下&#xff0c;当你的服务器在凌晨三点突然因为内存错误崩溃&#xff0c;或者磁盘在高峰期出现读写异常&a…...

第一步:你只需要改这里的所有参数

算数优化算法AOA&#xff0c;2021年新出的智能优化算法&#xff0c;结合SVM做回归拟合预测建模&#xff0c;代码内有详细的注释替换数据就可以使用上次实验室熬大夜调催化加氢产率的SVR模型差点怀疑人生&#xff1a;RBF核随便蒙C和gamma&#xff0c;MSE有时候0.01有时候飘到0.5…...

3步实战指南:轻松搭建抖音直播间弹幕数据抓取系统

3步实战指南&#xff1a;轻松搭建抖音直播间弹幕数据抓取系统 【免费下载链接】DouyinLiveWebFetcher 抖音直播间网页版的弹幕数据抓取&#xff08;2024最新版本&#xff09; 项目地址: https://gitcode.com/gh_mirrors/do/DouyinLiveWebFetcher 想象一下&#xff0c;你…...

JeecgBoot低代码开发平台终极实战指南:从零开始构建企业级应用

JeecgBoot低代码开发平台终极实战指南&#xff1a;从零开始构建企业级应用 【免费下载链接】jeecg-boot jeecgboot/jeecg-boot 是一个基于 Spring Boot 的 Java 框架&#xff0c;用于快速开发企业级应用。适合在 Java 应用开发中使用&#xff0c;提高开发效率和代码质量。特点是…...

RevokeMsgPatcher 2.1 终极指南:Windows平台微信QQ消息防撤回实战解决方案

RevokeMsgPatcher 2.1 终极指南&#xff1a;Windows平台微信QQ消息防撤回实战解决方案 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁&#xff08;我已经看到了&#xff0c;撤回也没用了&#xff09; 项目地址:…...

4步构建高效视频处理流水线:VideoFusion全功能指南

4步构建高效视频处理流水线&#xff1a;VideoFusion全功能指南 【免费下载链接】VideoFusion 一站式短视频拼接软件 无依赖,点击即用,自动去黑边,自动帧同步,自动调整分辨率,批量变更视频为横屏/竖屏 项目地址: https://gitcode.com/gh_mirrors/vi/VideoFusion 功能特性…...

NaViL-9B多模态提示词工程:提升图文理解准确率的10个实用技巧

NaViL-9B多模态提示词工程&#xff1a;提升图文理解准确率的10个实用技巧 1. 认识NaViL-9B多模态模型 NaViL-9B是一款原生支持多模态交互的大语言模型&#xff0c;能够同时处理文本和图像输入。与传统的纯文本模型不同&#xff0c;它可以直接"看懂"图片内容&#x…...

SEO_避开这些常见SEO误区,你的排名才能快速上升

<h2>SEO误区&#xff1a;为什么你的网站排名不上升</h2> <p>在当前竞争激烈的互联网环境中&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;是提升网站排名的关键。很多人在进行SEO优化时却常常犯下一些常见的SEO误区。这些误区不仅会让你的排名停滞不前…...

别再被‘小样本’难倒了!用Python的PyMC3库实战层次贝叶斯模型

用PyMC3解锁小样本分析&#xff1a;层次贝叶斯建模实战指南 当你的数据集像便利店冰柜里的酸奶——每个品类只有零星几瓶时&#xff0c;传统统计方法往往会束手无策。想象你正分析20个城市的新开门店周销售额&#xff0c;每个城市却只有3-5条数据记录。这时&#xff0c;层次贝叶…...