news 2026/7/19 2:35:03

csp信奥赛C++标准模板库STL案例应用19

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
csp信奥赛C++标准模板库STL案例应用19

csp信奥赛C++标准模板库STL案例应用19

priority_queue实践

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n − 1 n-1n−1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1 11，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3 33种果子，数目依次为1 11，2 22，9 99。可以先将1 11、2 22堆合并，新堆数目为3 33，耗费体力为3 33。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12 1212，耗费体力为12 1212。所以多多总共耗费体力= 3 + 12 = 15 =3+12=15=3+12=15。可以证明15 1515为最小的体力耗费值。

输入格式

共两行。

第一行是一个整数n ( 1 ≤ n ≤ 10 4 ) n(1\leq n\leq 10^4)n(1≤n≤104)，表示果子的种类数。

第二行包含n nn个整数，用空格分隔，第i ii个整数a i ( 1 ≤ a i ≤ 2 × 10 4 ) a_i(1\leq a_i\leq 2\times 10^4)ai​(1≤ai​≤2×104)是第i ii种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2 31 2^{31}231。

输入输出样例 1
输入 1
3 1 2 9
输出 1
15
说明/提示

对于30 % 30\%30%的数据，保证有n ≤ 10 3 n \le 10^3n≤103；

对于50 % 50\%50%的数据，保证有n ≤ 5 × 10 3 n \le 5\times10^3n≤5×103；

对于全部的数据，保证有n ≤ 10 4 n \le 10^4n≤104。

思路分析

这是一个经典的哈夫曼树（Huffman Tree）问题。要使得总体力消耗最小，需要每次合并当前最小的两堆果子。这样可以得到最优解。

贪心策略证明
  • 每次合并两堆果子，体力消耗为两堆果子的重量之和
  • 总消耗 = 所有非叶子节点的权值之和
  • 要让总消耗最小，就要让权值大的节点尽量在低层（合并次数少）
  • 哈夫曼算法保证了最优性：每次合并最小的两个数，这样大的数被合并的次数最少
时间复杂度

使用优先队列（最小堆）实现：

  • 建堆：O(n)
  • 每次取出两个最小元素并插入新元素：O(log n)
  • 总共进行 n-1 次合并：O(n log n)
  • 总复杂度：O(n log n)，对于 n ≤ 10^4 完全可行

代码实现

#include<bits/stdc++.h>usingnamespacestd;longlongn,x,ans=0;// n: 果子堆数// x: 临时变量，用于读取每堆果子的重量// ans: 总体力消耗值，用long long防止溢出// 使用最小优先队列（小根堆），每次可以快速获取最小的两个元素priority_queue<int,vector<int>,greater<int>>q;// greater<int> 使得队列顶部是最小元素intmain(){cin>>n;// 读取果子堆数// 读取每堆果子的重量并加入优先队列for(inti=1;i<=n;i++){cin>>x;q.push(x);// 将每堆果子的重量加入最小堆}// 当队列中还有多于一堆果子时，继续合并while(q.size()>1){// 取出当前最小的两堆果子inta=q.top();// 第一小的堆q.pop();intb=q.top();// 第二小的堆q.pop();intc=a+b;// 合并这两堆，消耗体力为a+bans+=c;// 累加体力消耗q.push(c);// 将新合并的堆加入队列}cout<<ans;// 输出最小体力消耗值return0;}

功能分析

核心功能
  1. 数据输入：读取果子堆数和每堆果子的重量
  2. 数据结构初始化：使用最小堆存储所有果子堆的重量
  3. 贪心合并：每次取出最小的两堆合并，直到只剩一堆
  4. 结果输出：输出总的最小体力消耗
关键点
  1. 优先队列的选择：使用priority_queue<int, vector<int>, greater<int>>实现最小堆
    • 默认是最大堆，需要指定greater<int>比较器
  2. 合并过程：
    • 每次合并最小的两堆，保证当前决策最优
    • 新合并的堆可能不是最小的，需要重新插入队列排序
  3. 边界处理：
    • n=1时，不需要合并，直接输出0
    • 代码中while(q.size() > 1)自动处理了这个边界情况
算法正确性
  • 这实际上是构建哈夫曼树的过程
  • 哈夫曼树是最优二叉树，保证了总路径长度（体力消耗）最小
  • 贪心选择性质：每次选择最小的两个数合并，不会影响后续决策的最优性
时间复杂度与空间复杂度
  • 时间复杂度：O(n log n)
    • 建堆 O(n)
    • n-1次合并，每次O(log n)
  • 空间复杂度：O(n)
    • 优先队列存储n个元素
适用场景
  • 需要多次合并，每次合并成本与合并对象大小相关的问题
  • 类似问题：文件合并、编码优化等

完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}
  • 一、CSP信奥赛C++通关学习视频课：
    • C++语法基础
    • C++语法进阶
    • C++算法
    • C++数据结构
    • CSP信奥赛数学
    • CSP信奥赛STL
  • 二、CSP信奥赛C++竞赛拿奖视频课：
    • 信奥赛csp-j初赛高频考点解析
    • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
  • 三、考级、竞赛刷题题单及题解：
    • GESP C++考级真题题解
    • CSP信奥赛C++初赛及复赛高频考点真题解析
    • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转


2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

  • 2025 csp-j 复赛真题及答案解析（最新更新）
  • 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
  • 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
  • 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
  • 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
  • 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
  • 2020 ~ 2024 csp 复赛真题题单及题解
  • 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
  • 2021 ~ 2024 csp-s 初赛高频考点解析
  • 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
  • 2024 csp-j 初赛真题及答案解析
  • 2025 csp-j 初赛真题及答案解析（最新更新）
  • 2025 csp-s 初赛真题及答案解析（最新更新）
  • 2025 csp-x (山东)初赛真题及答案解析(最新更新)
  • 2025 csp-x (江西)初赛真题及答案解析(最新更新)
  • 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

  • 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/7/18 17:17:30

手把手教你识别树莓派5和树莓派4的引脚差异

手把手教你识别树莓派5和树莓派4的引脚差异&#xff1a;别再被“兼容”骗了&#xff01; 你有没有遇到过这种情况&#xff1f; 把一个在树莓派4上跑得好好的HAT模块&#xff0c;插到全新的树莓派5上&#xff0c;结果IC设备找不到、ADC读数乱跳&#xff0c;甚至系统启动都卡住…

作者头像 李华
网站建设 2026/7/7 22:17:23

ClusterGAN深度解析：无监督学习中的聚类与生成双重突破

ClusterGAN深度解析&#xff1a;无监督学习中的聚类与生成双重突破 【免费下载链接】PyTorch-GAN PyTorch implementations of Generative Adversarial Networks. 项目地址: https://gitcode.com/gh_mirrors/py/PyTorch-GAN 在当今人工智能快速发展的时代&#xff0c;无…

作者头像 李华
网站建设 2026/7/18 10:25:03

如何在阿里云上部署TensorFlow训练任务？

如何在阿里云上部署 TensorFlow 训练任务&#xff1f; 今天&#xff0c;一个AI团队正面临这样的挑战&#xff1a;他们需要训练一个图像分类模型用于电商平台的商品识别&#xff0c;但本地GPU资源不足&#xff0c;训练一次耗时超过48小时&#xff0c;且无法支持多任务并行。更麻…

作者头像 李华
网站建设 2026/7/7 2:02:04

TensorFlow模型服务化：gRPC vs HTTP性能对比

TensorFlow模型服务化&#xff1a;gRPC vs HTTP性能对比 在构建高并发、低延迟的AI推理系统时&#xff0c;一个常被低估但至关重要的设计决策浮出水面&#xff1a;通信协议的选择。尤其是在使用 TensorFlow Serving 部署 ResNet、BERT 等复杂模型时&#xff0c;客户端与服务端之…

作者头像 李华
网站建设 2026/7/6 1:07:32

ESP32-CAM在Arduino中的低功耗模式配置核心要点

如何让 ESP32-CAM 真正“省电”&#xff1f;深度睡眠 外设断电实战指南你有没有遇到过这样的尴尬&#xff1a;满怀期待地把一个基于 ESP32-CAM 的监控小项目放进野外&#xff0c;结果电池三天就见底&#xff1f;明明查了资料说 ESP32 支持微安级功耗&#xff0c;怎么实测还是动…

作者头像 李华
网站建设 2026/7/6 1:07:30

如何在TensorFlow中实现注意力机制？

如何在TensorFlow中实现注意力机制&#xff1f; 在现代深度学习系统中&#xff0c;处理序列数据的能力已经成为衡量模型智能水平的关键指标。无论是翻译一段复杂的英文句子、生成连贯的对话回复&#xff0c;还是识别语音中的关键词&#xff0c;模型都需要从输入序列中精准提取相…

作者头像 李华