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

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树 定义 它是一种最优二叉树。通过构建带权路径长度最小的二叉树&#xff0c;经常用于数据压缩等领域。 运用情况 在数据压缩中&a…...

05 Pytorch 数据读取 + 二分类模型

05 Pytorch 数据读取 二分类模型05 Pytorch 数据读取 二分类模型05 Pytorch 数据读取 二分类模型 01 数据读取 DataLoader&#xff08;set作为参数&#xff09; 02 Dataset 从哪读&#xff0c;怎么读&#xff1f; 功能&#xff1a;数据从哪里读取&#xff1f; 如何读取…...

数据仓库之Kappa架构

Kappa架构是一种简化的数据处理架构&#xff0c;旨在处理实时数据流&#xff0c;解决传统Lambda架构中批处理和实时处理的复杂性。Kappa架构完全基于流处理&#xff0c;不区分批处理和实时处理&#xff0c;所有数据都是通过流处理系统进行处理。以下是对Kappa架构的详细介绍&am…...

ReactNative进阶(二十八)Metro

文章目录 一、前言二、Metro生命周期2.1 解析(Resolution)2.2 转换(Transformation)2.3 序列化(Serialization) 三、拓展阅读 一、前言 众所周知&#xff0c;Metro 是 React Native 默认的 JavaScript 打包模块。对于前端项目&#xff0c;打包工具已有webpack(大而全&#xff…...

python爬虫入门到精通路线

当谈及Python爬虫从入门到精通的路线时&#xff0c;我们可以将其分为几个关键阶段&#xff0c;每个阶段都有其特定的学习目标和内容。以下是一个清晰的路线规划&#xff1a; 1. 入门阶段 基础知识 学习Python的基础语法、数据类型、控制流等。了解基本的网络协议&#xff08…...

Java 笔记:常见正则使用

文章目录 Java 笔记&#xff1a;常见正则使用正则简介常用匹配年月日的时间匹配手机号码校验 参考文章 Java 笔记&#xff1a;常见正则使用 正则简介 正则表达式定义了字符串的模式。 正则表达式可以用来搜索、编辑或处理文本。 正则表达式并不仅限于某一种语言&#xff0c;但…...

vue 2.0项目中使用tinymce富文本框遇到的问题

安装Tinymce 现在tinymce-vue最新版本是4.0&#xff0c;用的vue3.0的了&#xff0c;所以搭建的vue2.0项目要使用之前的版本 ( 安装指定版本 ). 首先安装tinymce的vue组件&#xff0c;因为没有注册服务 npm install tinymce/tinymce-vue2.0.0 -S接着安装tinymce: npm install…...

【STM32+FPGA】先进算力+强安全+边缘AI,64位STM32MP2聚焦工业4.0应用

工业应用数字化和智能化程度&#xff0c;是衡量新质生产力的重要标准。STM32最新一代64位微处理器STM32MP2凭借先进算力、丰富接口和高安全性&#xff0c;为高性能和高度互联的工业4.0应用赋能。 STM32MP2四大关键特性&#xff0c;为工业4.0应用赋能 STM32MP2系列的第一颗产品S…...

Git 和 TortoiseGit 安装和配置(图文详解)

使用git&#xff0c;需要在Windows上需要安装两个软件&#xff1a;1&#xff09;Git 2&#xff09;TortoiseGit 若需要&#xff0c;可以下载TortoiseGit汉化语言包。 注意&#xff1a;tortoiseGit是在安装了Git的基础上运行的&#xff0c;所以需要先安装Git&#xff0c;后安装…...

OpenAI CTO谈GPT-5将达博士生智力水平;斯坦福评估排名前十两款来自中国

&#x1f989; AI新闻 &#x1f680; OpenAI CTO谈GPT-5将达博士生智力水平 摘要&#xff1a;美国达特茅斯工程学院采访了OpenAI首席技术官米拉・穆拉蒂&#xff0c;她表示GPT-4的智力相当于高中生&#xff0c;而GPT-5将在一年半后发布&#xff0c;预计达到博士生水平。穆拉蒂…...

焦化超低排平台组成部分

焦化行业作为重工业的重要组成部分&#xff0c;其环保问题一直备受关注。近年来&#xff0c;随着环保意识的提升和技术的不断进步&#xff0c;朗观视觉焦化超低排平台应运而生&#xff0c;成为推动焦化行业绿色发展的重要力量。本文将深入剖析焦化超低排平台的组成部分&#xf…...

鸿蒙 navigation路由跳转,页面struct 下的生命周期、onShow、onHidden等不会触发问题

经常用安卓思维考虑问题&#xff0c;用习惯了Router方式跳转&#xff0c;但是官方推荐用 navigation&#xff0c;当然它有它的有点&#xff0c; 也有小瑕疵&#xff0c;用了api11 后 发现 navigation路由跳转 &#xff0c;只要被它包裹的跳转到下页面的&#xff0c;有些生命周期…...

BUUCTF [CISCN2019 华北赛区 Day2 Web1] Hack World

1、通过题目&#xff0c;可以知道该题目为SQL注入类型&#xff1a; 2、判断注入类型为数字注入&#xff1a; 3、通过BP抓包&#xff0c;来判断注入点。 字典爆破发现常规的注入方式都被过滤。 4、因此可以尝试通过布尔盲注的方式来得到flag。编写脚本得到flag import requests…...

wsl2平台鸿蒙全仓docker编译环境快速创建方法

文章目录 1 文章适用范围&#xff1a;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…...

商业秘密侵权

一、商业秘密侵权行为 &#xff08;一&#xff09;员工违规获取并使用企业后台用户行为数据构成商业秘密侵权 &#xff08;二&#xff09;离职员工将新单位“冒名顶替”为原单位构成对原单位商业秘密的侵犯 二、商业秘密侵权主体 &#xff08;一&#xff09;主体范围界定&a…...

高通安卓12-固件升级

下载步骤 第一步 格式化 「下载一次即可&#xff1b;能开机能下载的板子 忽略这一步&#xff0c;直接执行第二步即可」 QFIL工具配置为UFS类型&#xff0c;勾选Provision&#xff0c;如下图&#xff1a; Programmer选择prog_firehose_ddr.elf&#xff0c;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. &#xff08;可选&#xff09;配置其他开发工具 在Windows系统中搭建Python 3.11环境&#xff0c;可以按照以下步骤进行&#xff0c;以确保过程清晰且详细&#xff1a; 1. 下载Python 3.12安装包 打开浏览器&a…...

植物大战僵尸杂交版如何手动修改金币钻石数

前言 最近在玩植物大战僵尸杂交版&#xff0c;非常好玩&#xff0c;但是刷钻石真的好慢&#xff01;只能在排山倒海里眼巴巴等着黄金吞噬者产钻石qaq 但是好歹咱是学CS的&#xff0c;怎会被这点困难难住&#xff01;挑战不用修改器手动修改配置文件&#xff01; 原参考文章&…...

Salia PLCC cPH2 远程命令执行漏洞(CVE-2023-46359)

漏洞描述 Salia PLCC cPH2 v1.87.0 及更早版本中存在一个操作系统命令注入漏洞&#xff0c;该漏洞可能允许未经身份验证的远程攻击者通过传递给连接检查功能的特制参数在系统上执行任意命令。 产品界面 fofa语法 "Salia PLCC" POC GET /connectioncheck.php?ip1…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

【Ftrace 专栏】Ftrace 参考博文

ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...

背包问题双雄:01 背包与完全背包详解(Java 实现)

一、背包问题概述 背包问题是动态规划领域的经典问题&#xff0c;其核心在于如何在有限容量的背包中选择物品&#xff0c;使得总价值最大化。根据物品选择规则的不同&#xff0c;主要分为两类&#xff1a; 01 背包&#xff1a;每件物品最多选 1 次&#xff08;选或不选&#…...