现在有 n 堆果子，每堆果子的重量为 ai​，你要进行 n−1 次合并。每次合并会把两堆果子合并成一堆果子，合并需要花费的体力为这两堆果子的重量之和，合并后果子的重量也为这两堆果子的重量之和。现在让你求出 n−1 次合并花费的最小总体力。

思路

贪心思路

首先，很容易想到一个贪心：每次取重量最小的两堆果子，再取合并后重量最小的两堆果子，直到只有一堆果子为止。

证明过程

现在就要证明这个贪心，这里不妨先证明小范围贪心正确，再证明推导到大范围正确，就可以证明这个贪心正确。

step 1: 证明小范围贪心正确

假设现在只有 3 堆果子，果子的数量分别为 a,b,c，假设 a≤b≤c（a,b,c 的顺序与答案无关），现在开始需要先取 a,b 一定是最优的。

第一种情况：先取 a,b，最终答案为 (a+b)+(a+b+c)=2a+2b+c。

第二种情况：先取 a,c，最终答案为 (a+c)+(a+b+c)=2a+b+2c。

第二种情况：先取 b,c，最终答案为 (b+c)+(a+b+c)=a+2b+2c。

现在需要比较 2a+2b+c,2a+b+2c,a+2b+2c 的大小关系。

因为三个式子都含有 a+b+c，所以可以消掉 把三个式子同时减去 a+b+c。

现在问题就变成了比较 a+b,a+c,b+c 的大小关系。

因为 a≤b≤c，所以 a+b≤a+c≤b+c。

所以第一种情况（先取 a,b）一定是最优的。

再举个例子说明，比如 a=3,b=5,c=9。

第一种情况（先取 a,b）的答案是 2a+2b+c=25。

第二种情况（先取 a,c）的答案是 2a+b+2c=29。

第三种情况（先取 b,c）的答案是 a+2b+2c=31。

通过比较也可以发现第一种情况（先取 a,b）是最优的。

step 2: 证明推导到大范围也正确

假设有 n(n>3) 堆果子，合并完 n−3 次之后，还剩 3 堆果子，可以用类似的方法证明取重量最小的两堆果子是最优的。

因此，取重量最小的两堆果子一定是最优的。

代码实现

选择 priority_queue 及使用方法

现在需要一种数据结构，能动态找到数据结构中最小值和次小值，并删除他们，再插入他们的和。

我这里采用的是 stl 库中的 priority_queue（优先队列，也被称为堆），可以在 O(logn) 的时间复杂度内插入、查询优先队列中最大 / 最小值、删除优先队列中最大 / 最小值。

priority_queue 的使用方法如下。

//定义方法
#include <queue>//需要的头文件
priority_queue<int>q1;//定义一个大根堆，查询和插入的是最大值
priority_queue<int, vector<int>, greater<int>>q1;//定义一个小根堆，查询和插入的是最小值

//使用方法
q1.push(7);//往大根堆内插入一个值7
q1.push(4);//插入4
q1.push(12);//插入12
q1.top();//查询大根堆内的最大值，此时返回值为12
q1.pop();//删除大根堆内的最大值（删除12），没有返回值
q1.size();//查询优先队列数的个数，此时返回值为2
q1.top();//此时的最大值变成了7，所以返回7

//小根堆的使用方法与大根堆的使用方法一样
q2.push(9);//插入一个数9
q2.top();//查询小根堆内最小值，返回9
q2.push(1);//插入1
q2.pop();//删除小根堆内最小值（删除1），同样没有返回值
q2.push(3);//插入3
q1.size();//查询优先队列数的个数，此时返回值为2
q2.top();//此时小根堆内的值为3和9，返回3

算法流程

输入输出我就不在这里说了，请读者自行思考。 1. 定义优先队列（小根堆）。 2. 将每堆果子的重量放进优先队列。 3. 取出小根堆中最小值和次小值，统计答案，放入他们的和。 4. 重复步骤三，直到只有一堆果子。

Code（只展示关键代码）

priority_queue<int, vector<int>, greater<int>>q;//1.定义小根堆
//2.将每堆果子的重量放进优先队列
//我在这里不放了，请读者自行思考
long long sum = 0;
while (q.size() > 1){//4.重复步骤三，直到只有一堆果子。
    int a1 = q.top();
    q.pop();
    int a2 = q.top();
    q.pop();
    //取出a1和a2，即最小值和次小值
    sum += a1 + a2;//统计答案
    q.push(a1 + a2);//放入他们的和
}