题目描述

第 i 块木板的长度为 Li（1≤ Li ≤50000） 。John 买了一块很长 的木板，其长度正好等于所需要的 N 块木板长度总和。接下来当然要把它切割 开，假定切割木板的过程中没有任何损失。 切割一块木板的费用正比于木板的长度，比如，一块木板的长度为 21，那 么锯开它的费用就是 21 美分。John 可以自由的决定切割木板的顺序以及每次 切割的位置。很显然，按照不同的顺序切割木板最终的花费是完全不一样的，请 你帮助 John 计算出为了得到他所想要的木板，最少花费为多少？

思路

建一个小根堆，每次取两个数，然后加起来存入堆中，并更新ans
long long!!!!!!!

#include <stdio.h>
#include <queue>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> > q;
int main()
{
    long long n;
    scanf("%d",&n);
    for (long long i=1;i<=n;i++)
    {
        long long x;
        scanf("%d",&x);
        q.push(x);
    }
    long long ans=0;
    for (long long i=1;i<n;i++)
    {
        long long x=q.top();
        q.pop();
        long long y=q.top();
        q.pop();
        ans+=x+y;
        q.push(x+y);
    }
    printf("%lld\n",ans);
}