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…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
