瑞瑞的木板（洛谷P1334 ）
题目背景
瑞瑞想要亲自修复在他的一个小牧场周围的围栏。
题目描述
他测量栅栏并发现他需要 n 根木板，每根的长度为整数 li。于是，他买了一根足够长的木板，长度为所需的 n 根木板的长度的总和，他决定将这根木板切成所需的 n 根木板（瑞瑞在切割木板时不会产生木屑，不需考虑切割时损耗的长度)。
瑞瑞切割木板时使用的是一种特殊的方式，这种方式在将一根长度为 x 的木板切为两根时，需要消耗 x 个单位的能量。瑞瑞拥有无尽的能量，但现在提倡节约能量，所以作为榜样，他决定尽可能节约能量。显然，总共需要切割 (n−1) 次，问题是，每次应该怎么切呢？请编程计算最少需要消耗的能量总和。
输入格式
输入的第一行是整数，表示所需木板的数量 n。
第 2 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数 li 代表第 i 根木板的长度 li。
输出格式
一个整数，表示最少需要消耗的能量总和。
输入输出样例
输入 #1复制运行
3 8 5 8
输出 #1复制运行
34
说明/提示
输入输出样例 1 解释
将长度为 21 的木板，第一次切割为长度为 8 和长度为 13 的，消耗 21 个单位的能量，第二次将长度为 13 的木板切割为长度为 5 和 8 的，消耗 13 个单位的能量，共消耗 34 个单位的能量，是消耗能量最小的方案。
数据规模与约定
- 对于 100% 的数据，保证 1≤n≤2×104，1≤li≤5×104。
1. 题目简介
本题是一个经典的“合并果子”或“哈夫曼编码”类型的变种问题。
题目要求将一根长木板切割成若干块给定长度的小木板，每次切割的代价是当前木板的长度。我们需要求出完成所有切割所需的最小总代价。
逆向思维：切割过程极其复杂，我们可以将其逆向思考为“合并”过程——将N块小木板每次两两合并，最终还原成一根长木板。每次合并的代价就是两块木板长度之和。问题转化为：如何通过合并策略，使得总消耗能量最小。
2. 解题思路
核心策略：贪心
为了让总代价最小，我们需要让长度长（权重很大）的木板尽可能少参与合并运算，而长度短的木板可以多次参与运算。
因此，我们的贪心策略是：每次都从当前所有木板中，取出长度最小的两块进行合并。
数据结构选择
由于每次合并后会产生一个新的木板长度，这个新长度需要放回集合中，并且可能会改变集合的大小顺序。
如果使用数组排序：每次合并后都要重新排序，时间复杂度会达到O(N^2)，容易超时。
最佳选择：使用优先队列 (最小堆)。
priority_queue可以以 O(log N) 的复杂度自动维护数据的有序性。取最小值、插入新值都非常高效。
算法流程
特判：如果只有 1 块木板，不需要切割，输出 0。
初始化：建立一个
greater类型的优先队列（小根堆），将所有初始木板长度入队。循环合并：当队列中元素大于 1 个时：
取出堆顶（最小）元素a，弹出。
再次取出堆顶（次小）元素b，弹出。
计算代价
sum+=a+b。将合并后的新长度
a+b重新推入堆中。
输出：最终的
sum即为答案。
3. 核心总结
算法本质：这就是经典的哈夫曼树构造过程。通过贪心策略，保证权值越小的节点离根越远（参与运算次数越多），权值越大的节点离根越近，从而使带权路径长度（WPL）最小。
复杂度分析：
时间复杂度：每一轮合并涉及两次
pop和一次push，操作次数为N-1次，堆操作复杂度为 O(log N)，总时间复杂度为O(N log N)。空间复杂度：需要存储N个元素，为O(N)。
避坑指南：
数据类型：累加的代价
sum可能会超过int范围，必须使用long long。边界条件：注意N=1的情况，此时不需要消耗能量。
堆的定义：STL 默认是大根堆，记得加上
vector<long long>, greater<long long>定义为小根堆。
解题总结：
遇到“合并代价最小”类问题，直接用小根堆，每次取俩最小、合二为一、扔回堆里，直到只剩一个，记得观察数据范围开
long long。
//分割本质倒过来就是合并，这道题本质上是一道哈夫曼树，要让大数参与合并的次数尽可能少 #include <iostream> #include <queue> using namespace std; priority_queue<long long,vector<long long>,greater<long long>> q;//最小堆 int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; if(n==1){//如果只有一根木板 不需要切 cout<<0; return 0; } long long sum=0;//消耗的总能量 for(int i=1;i<=n;i++){//把所有要切出来的木板长度入队 int tmp; cin>>tmp; q.push(tmp); } while(q.size()!=1){//当已经所有木板合并成一根木板就不要合并了 long long a=q.top();//每次合并里面最小的两根木板，这样越大木板参与合并的次数就会越少，那总能量消耗就会小 q.pop(); long long b=q.top(); q.pop(); q.push(a+b); sum=sum+a+b; } cout<<sum; return 0; }