TensorFlow模型API弹性伸缩配置
2025/12/27 12:09:38
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;}功能分析
核心功能
- 数据输入：读取果子堆数和每堆果子的重量
- 数据结构初始化：使用最小堆存储所有果子堆的重量
- 贪心合并：每次取出最小的两堆合并，直到只剩一堆
- 结果输出：输出总的最小体力消耗
关键点
- 优先队列的选择：使用
priority_queue<int, vector<int>, greater<int>>实现最小堆- 默认是最大堆，需要指定
greater<int>比较器
- 默认是最大堆，需要指定
- 合并过程：
- 每次合并最小的两堆，保证当前决策最优
- 新合并的堆可能不是最小的，需要重新插入队列排序
- 边界处理：
- 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;}