news 2026/1/30 2:47:12

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/1/28 2:22:37

PaddlePaddle镜像中的评估指标怎么解读？准确率陷阱提醒

PaddlePaddle镜像中的评估指标怎么解读&#xff1f;准确率陷阱提醒 在工业级AI系统不断落地的今天&#xff0c;一个看似不起眼的问题却频频导致模型“上线即翻车”——我们太容易被“高准确率”蒙蔽了双眼。尤其是在使用PaddlePaddle官方Docker镜像进行训练和验证时&#xff0c…

作者头像 李华
网站建设 2026/1/27 20:16:44

12.27 脚本网页 GITHUB推送教程

一 ,GITHUB是知名网站代码托管平台&#xff0c;类似网盘二 ,下面命令可以帮你在手机termux上&#xff0c;把代码推送上去三&#xff0c;详细内容已做成&#xff0c;网页随时查。稍作修改&#xff0c;可以集成到个人网站<!DOCTYPE html> <html lang"zh-CN"&g…

作者头像 李华
网站建设 2026/1/29 11:36:58

Nunchaku FLUX.1-Krea-dev量化模型：让AI图像生成走进普通电脑

Nunchaku FLUX.1-Krea-dev量化模型&#xff1a;让AI图像生成走进普通电脑 【免费下载链接】nunchaku-flux.1-krea-dev 项目地址: https://ai.gitcode.com/hf_mirrors/nunchaku-tech/nunchaku-flux.1-krea-dev 在AI图像生成技术快速发展的今天&#xff0c;许多创作者面临…

作者头像 李华
网站建设 2026/1/29 12:35:36

【大模型部署新突破】：Open-AutoGLM一键部署脚本开源，速领！

第一章&#xff1a;Open-AutoGLM 一键部署概述Open-AutoGLM 是一个面向大语言模型推理与自动化任务的开源框架&#xff0c;支持快速部署具备自然语言理解与代码生成能力的 GLM 系列模型。其核心优势在于提供了一键式本地化部署方案&#xff0c;大幅降低开发者在环境配置、依赖管…

作者头像 李华
网站建设 2026/1/25 3:18:57

PaddlePaddle镜像支持语音合成TTS吗？Parakeet模块详解

PaddlePaddle镜像支持语音合成TTS吗&#xff1f;Parakeet模块详解 在智能客服、有声读物和语音助手日益普及的今天&#xff0c;高质量的中文语音合成&#xff08;Text-to-Speech, TTS&#xff09;已成为人机交互的关键能力。然而&#xff0c;许多开发者在实际项目中常面临一个现…

作者头像 李华
网站建设 2026/1/29 21:16:48

Stata数据分析终极指南：从零基础到实战应用

Stata数据分析终极指南&#xff1a;从零基础到实战应用 【免费下载链接】stata Stata Commands for Data Management and Analysis 项目地址: https://gitcode.com/gh_mirrors/st/stata Stata作为世界银行维护的统计软件包&#xff0c;在数据科学领域占据着重要地位。本…

作者头像 李华