当前位置: 首页 > 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架构。实时数…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...