Cut

思路

这题和POJ 3253很像，有兴趣可以去看看

可以试着反向思维考虑，将n个长度为1的序列合并成一个长度为n的序列,合并的代价就是合并前的两个序列之和

最佳的合并方法应该是尽可能多的合并长的木板，所以最优的策略应该是将目前所有序列中长度最大和次大的序列合并

不妨将原序列按降序排列，每次取出最大的两个序列，序列合并后再加入到原序列，一直循环即可

由于只需要从序列中取出最大的两个，所以可以用优先队列高效实现，建立一个大根堆，模拟过程就好

代码（优先队列做法）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
priority_queue<ll> q;
int main(){
    int n = read();
    for(int i = 0 ; i < n  ;++i){
        ll tmp = read();
        q.push(tmp);
    }
    ll ans = 0;
    while(q.size() > 1){
        ll tmp  = q.top();q.pop();
        tmp += q.top();q.pop();
        ans += tmp;
        q.push(tmp);
    }
    cout<<ans<<endl;
}

仔细思考上述过程发现将合并后的序列入堆后再次取出两个序列,上一次合并后的序列肯定会被取出。
统计一下可以发现n个长度为1的序列中，最大和次大的长度的序列总计取出了n-1次，次次大的取出了n-2次，最小的序列取出了1次，所以只需要排序后一个乘法就好

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll a[100005];
int main(){
    int n = read();
    for(int i = 1 ; i <= n  ;++i){
        a[i] = read();
    }
    ll ans = 0;
    sort(a+1,a+1+n);
     for(int i = 1 ; i <= n ; ++i){
         ans += a[i]*i;
     }
    ans -= a[n];
    cout<<ans<<endl;
}