Huffman树——AcWing 148. 合并果子
目录
Huffman树
定义
运用情况
注意事项
解题思路
AcWing 148. 合并果子
题目描述
运行代码
代码思路
其它代码
代码思路
Huffman树
定义
它是一种最优二叉树。通过构建带权路径长度最小的二叉树,经常用于数据压缩等领域。
运用情况
- 在数据压缩中,如赫夫曼编码,可实现高效的无损数据压缩。
- 在信息传输中,减少传输的数据量。
注意事项
- 权值的确定要合理。
- 构建过程要准确,确保得到最优树结构。
解题思路
- 首先根据给定的权值构建初始森林。
- 不断选取权值最小的两个节点合并成一个新节点,新节点的权值为两节点权值之和。
- 重复这个过程直到只剩下一个节点,该节点就是 Huffman 树的根节点。
例如,假设有字符 A、B、C、D,权值分别为 5、7、2、8,构建 Huffman 树的过程如下:先选取权值 2 和 5 的节点 C 和 A 合并,得到新节点权值 7,此时森林中有节点 B(权值 7)、新节点(权值 7)和 D(权值 8),再选取两个权值 7 的节点合并,最后和 D 合并得到最终的 Huffman 树。通过这样的树结构可以生成相应的编码来实现数据压缩等目的。
AcWing 148. 合并果子
题目描述
AcWing 148. 合并果子 - AcWing

运行代码
#include <iostream>
#include <queue>
using namespace std;
int main() {int n;cin >> n;priority_queue<int, vector<int>, greater<int>> pq;for (int i = 0; i < n; i++) {int num;cin >> num;pq.push(num);}int total = 0;while (pq.size() > 1) {int a = pq.top();pq.pop();int b = pq.top();pq.pop();total += a + b;pq.push(a + b);}cout << total << endl;return 0;
}
代码思路
- 首先,定义了变量
n用于接收果子的种类数。 - 创建了一个小顶堆(优先队列)
pq,用于存储各种果子的数量。 - 通过循环输入每种果子的数量并将其压入堆中。
- 然后,在一个循环中,只要堆中元素数量大于 1,就不断取出堆顶的两个最小元素
a和b,将它们的和累加到total中,这就是合并这两堆果子所消耗的体力,然后将合并后的新数量a+b再压入堆中。这样不断进行合并操作,直到堆中最后只剩下一个元素,此时total中存储的就是最小体力耗费值。最后将其输出。
其它代码
#include <iostream>
#include <queue>
using namespace std;
int main()
{int n; cin >> n;priority_queue<int, vector<int>, greater<int>> heap;while(n--){int x; cin >> x;heap.push(x);}int res = 0;while(heap.size() > 1){int a = heap.top();heap.pop();int b = heap.top();heap.pop();res += a + b;heap.push(a + b);}cout << res << endl;return 0;
}
代码思路
- 首先定义了变量
n用于接收果子的种类数。 - 创建了一个小顶堆(优先队列)
heap。 - 通过一个循环读取每种果子的数量并将其压入堆中。
- 然后定义了结果变量
res并初始化为 0。 - 接着进入一个循环,只要堆中元素数量大于 1,就执行以下操作:从堆顶取出两个元素
a和b(这两个是当前堆中最小的两个元素),将它们的和累加到res中(这就是合并这两堆果子消耗的体力),然后将合并后的新值a+b再压入堆中,这样不断地合并堆中的元素,直到最后堆中只剩下一个元素。 - 最后输出计算得到的最小体力耗费值
res。
相关文章:
Huffman树——AcWing 148. 合并果子
目录 Huffman树 定义 运用情况 注意事项 解题思路 AcWing 148. 合并果子 题目描述 运行代码 代码思路 其它代码 代码思路 Huffman树 定义 它是一种最优二叉树。通过构建带权路径长度最小的二叉树,经常用于数据压缩等领域。 运用情况 在数据压缩中&a…...
05 Pytorch 数据读取 + 二分类模型
05 Pytorch 数据读取 二分类模型05 Pytorch 数据读取 二分类模型05 Pytorch 数据读取 二分类模型 01 数据读取 DataLoader(set作为参数) 02 Dataset 从哪读,怎么读? 功能:数据从哪里读取? 如何读取…...
数据仓库之Kappa架构
Kappa架构是一种简化的数据处理架构,旨在处理实时数据流,解决传统Lambda架构中批处理和实时处理的复杂性。Kappa架构完全基于流处理,不区分批处理和实时处理,所有数据都是通过流处理系统进行处理。以下是对Kappa架构的详细介绍&am…...
ReactNative进阶(二十八)Metro
文章目录 一、前言二、Metro生命周期2.1 解析(Resolution)2.2 转换(Transformation)2.3 序列化(Serialization) 三、拓展阅读 一、前言 众所周知,Metro 是 React Native 默认的 JavaScript 打包模块。对于前端项目,打包工具已有webpack(大而全ÿ…...
python爬虫入门到精通路线
当谈及Python爬虫从入门到精通的路线时,我们可以将其分为几个关键阶段,每个阶段都有其特定的学习目标和内容。以下是一个清晰的路线规划: 1. 入门阶段 基础知识 学习Python的基础语法、数据类型、控制流等。了解基本的网络协议(…...
Java 笔记:常见正则使用
文章目录 Java 笔记:常见正则使用正则简介常用匹配年月日的时间匹配手机号码校验 参考文章 Java 笔记:常见正则使用 正则简介 正则表达式定义了字符串的模式。 正则表达式可以用来搜索、编辑或处理文本。 正则表达式并不仅限于某一种语言,但…...
vue 2.0项目中使用tinymce富文本框遇到的问题
安装Tinymce 现在tinymce-vue最新版本是4.0,用的vue3.0的了,所以搭建的vue2.0项目要使用之前的版本 ( 安装指定版本 ). 首先安装tinymce的vue组件,因为没有注册服务 npm install tinymce/tinymce-vue2.0.0 -S接着安装tinymce: npm install…...
【STM32+FPGA】先进算力+强安全+边缘AI,64位STM32MP2聚焦工业4.0应用
工业应用数字化和智能化程度,是衡量新质生产力的重要标准。STM32最新一代64位微处理器STM32MP2凭借先进算力、丰富接口和高安全性,为高性能和高度互联的工业4.0应用赋能。 STM32MP2四大关键特性,为工业4.0应用赋能 STM32MP2系列的第一颗产品S…...
Git 和 TortoiseGit 安装和配置(图文详解)
使用git,需要在Windows上需要安装两个软件:1)Git 2)TortoiseGit 若需要,可以下载TortoiseGit汉化语言包。 注意:tortoiseGit是在安装了Git的基础上运行的,所以需要先安装Git,后安装…...
OpenAI CTO谈GPT-5将达博士生智力水平;斯坦福评估排名前十两款来自中国
🦉 AI新闻 🚀 OpenAI CTO谈GPT-5将达博士生智力水平 摘要:美国达特茅斯工程学院采访了OpenAI首席技术官米拉・穆拉蒂,她表示GPT-4的智力相当于高中生,而GPT-5将在一年半后发布,预计达到博士生水平。穆拉蒂…...
焦化超低排平台组成部分
焦化行业作为重工业的重要组成部分,其环保问题一直备受关注。近年来,随着环保意识的提升和技术的不断进步,朗观视觉焦化超低排平台应运而生,成为推动焦化行业绿色发展的重要力量。本文将深入剖析焦化超低排平台的组成部分…...
鸿蒙 navigation路由跳转,页面struct 下的生命周期、onShow、onHidden等不会触发问题
经常用安卓思维考虑问题,用习惯了Router方式跳转,但是官方推荐用 navigation,当然它有它的有点, 也有小瑕疵,用了api11 后 发现 navigation路由跳转 ,只要被它包裹的跳转到下页面的,有些生命周期…...
BUUCTF [CISCN2019 华北赛区 Day2 Web1] Hack World
1、通过题目,可以知道该题目为SQL注入类型: 2、判断注入类型为数字注入: 3、通过BP抓包,来判断注入点。 字典爆破发现常规的注入方式都被过滤。 4、因此可以尝试通过布尔盲注的方式来得到flag。编写脚本得到flag import requests…...
wsl2平台鸿蒙全仓docker编译环境快速创建方法
文章目录 1 文章适用范围:2 WSL环境安装3 镜像迁移非C盘4 Docker环境准备4.1 docker用户组和用户创建4.2 Docker环境配置4.2.1 Ubuntu下安装docker工具4.2.2 鸿蒙Docker环境安装4.2.3 鸿蒙全仓代码拉取编译 5 鸿蒙全仓代码的更新策略6 参考文献7 FAQ7.1 缺头文件xcr…...
商业秘密侵权
一、商业秘密侵权行为 (一)员工违规获取并使用企业后台用户行为数据构成商业秘密侵权 (二)离职员工将新单位“冒名顶替”为原单位构成对原单位商业秘密的侵犯 二、商业秘密侵权主体 (一)主体范围界定&a…...
高通安卓12-固件升级
下载步骤 第一步 格式化 「下载一次即可;能开机能下载的板子 忽略这一步,直接执行第二步即可」 QFIL工具配置为UFS类型,勾选Provision,如下图: Programmer选择prog_firehose_ddr.elf,Provision Xml选择prov…...
我的常见问题记录
1,maven在idea工具可以正常使用,在命令窗口执行出现问题 代码: E:\test-hello\simple-test>mvn clean compile [INFO] Scanning for projects... [WARNING] [WARNING] Some problems were encountered while building the effective model for org.consola:simple-test:jar…...
Python 3.12 环境搭建(Windows版)
目录 1. 下载Python 3.12安装包2. 安装Python 3.123. 验证安装5. (可选)配置其他开发工具 在Windows系统中搭建Python 3.11环境,可以按照以下步骤进行,以确保过程清晰且详细: 1. 下载Python 3.12安装包 打开浏览器&a…...
植物大战僵尸杂交版如何手动修改金币钻石数
前言 最近在玩植物大战僵尸杂交版,非常好玩,但是刷钻石真的好慢!只能在排山倒海里眼巴巴等着黄金吞噬者产钻石qaq 但是好歹咱是学CS的,怎会被这点困难难住!挑战不用修改器手动修改配置文件! 原参考文章&…...
Salia PLCC cPH2 远程命令执行漏洞(CVE-2023-46359)
漏洞描述 Salia PLCC cPH2 v1.87.0 及更早版本中存在一个操作系统命令注入漏洞,该漏洞可能允许未经身份验证的远程攻击者通过传递给连接检查功能的特制参数在系统上执行任意命令。 产品界面 fofa语法 "Salia PLCC" POC GET /connectioncheck.php?ip1…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
