P1334 瑞瑞的木板网页链接P1334 瑞瑞的木板题目背景瑞瑞想要亲自修复在他的一个小牧场周围的围栏。题目描述他测量栅栏并发现他需要n nn根木板每根的长度为整数l i l_ili​。于是他买了一根足够长的木板长度为所需的n nn根木板的长度的总和他决定将这根木板切成所需的n nn根木板瑞瑞在切割木板时不会产生木屑不需考虑切割时损耗的长度)。瑞瑞切割木板时使用的是一种特殊的方式这种方式在将一根长度为x xx的木板切为两根时需要消耗x xx个单位的能量。瑞瑞拥有无尽的能量但现在提倡节约能量所以作为榜样他决定尽可能节约能量。显然总共需要切割( n − 1 ) (n-1)(n−1)次问题是每次应该怎么切呢请编程计算最少需要消耗的能量总和。输入格式输入的第一行是整数表示所需木板的数量n nn。第2 22到第( n 1 ) (n 1)(n1)行每行一个整数第( i 1 ) (i 1)(i1)行的整数l i l_ili​代表第i ii根木板的长度l i l_ili​。输出格式一个整数表示最少需要消耗的能量总和。输入输出样例 #1输入 #13 8 5 8输出 #134说明/提示输入输出样例 1 解释将长度为21 2121的木板第一次切割为长度为8 88和长度为13 1313的消耗21 2121个单位的能量第二次将长度为13 1313的木板切割为长度为5 55和8 88的消耗13 1313个单位的能量共消耗34 3434个单位的能量是消耗能量最小的方案。数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 2 × 10 4 1\le n \le 2 \times 10^41≤n≤2×1041 ≤ l i ≤ 5 × 10 4 1 \leq l_i \leq 5 \times 10^41≤li​≤5×104。解题思路本题是经典的哈夫曼树贪心问题与合并果子模型完全一致。切割长木板的最小能耗等价于将所有目标木板长度两两合并每次合并的代价为两数之和总代价最小。采用小根堆优先队列维护当前所有木板长度每次取出堆顶两个最小的数值计算合并代价并累加到总能耗中再将合并后的新长度放回堆中。重复操作n − 1 n-1n−1次共需切割n − 1 n-1n−1次最终累加的结果就是最少消耗的能量。算法时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)高效适配题目数据约束。总结核心逻辑切割木板的最小能耗 哈夫曼树的总权值贪心合并最小元素最优。关键操作小根堆存储木板长度、循环合并最小两个元素、累加合并代价。效率保障优先队列的对数级操作无冗余计算完美处理2 × 10 4 2×10^42×104规模数据。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll ans0,n,t;priority_queuell,vectorll,greaterlla;scanf(%lld,n);for(ll i1;in;i){scanf(%lld,t);a.push(t);}for(ll i1;in-1;i){ll ca.top();a.pop();ll da.top();a.pop();anscd;a.push(cd);}printf(%lld,ans);return0;}