核心思想

• 每次取出两个最小的堆，然后这两堆合成一个新堆，再重新选出两个最小的 ，然后再合成一个新的 ，如此往复，直到就剩下一个。
• 注意要记下 每次合成 的“代价”。

理解思想的小栗子

例如:
有 3 种果子，数目依次为 1，2，9。可以先将 1、2堆合并，新堆数目为 3，耗费体力为 3。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。
所以达达总共耗费体力=3+12=15。
可以证明 15为最小的体力耗费值。

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n,x;
priority_queue<int, vector<int>, greater<int>> heap; // 小根堆

int main()
{
    cin>>n;
    while (n -- )cin>>x,heap.push(x);

    int res=0;
    while(heap.size()>1){
        int a = heap.top();heap.pop();
        int b = heap.top();heap.pop();
        res+=(a+b);
        heap.push(a+b);
    }

    cout << res;
    return 0;
}