题解 | #搬水果#

/// 注意   :  此动态 规划 是 只能合并相邻的两堆
/// 哈夫曼树  是 每次合并可以 从堆中 任意挑选 两堆


// ///状态表示: 集合: 第i堆到第j堆 合并的所有情况   属性: 代价最小
// /// 状态计算 : f[i][j] = min(f[i][k]+f[k][j]) + s[j]-s[i-1]

// //// 为什么动态规划 AC不了啊
// // 我这个 动规 有问题吗
// #include "iostream"
// #include "cstdio"
// #include "algorithm"
// using namespace std;
// const int N = 10010;
// int n;
// int f[N][N];
// int s[N];
// int main() {
//     cin >> n;
//     for (int i = 1; i <= n; i++) {
//         scanf("%d", &s[i]);
//         s[i] += s[i - 1];
//     }
//     for (int len = 2; len <= n; len++) {
//         for (int i = 1; i + len - 1 <= n; i++) {
//             int l = i, r = i + len - 1;
//             f[l][r] = 1e9;
//             for (int k = l; k < r; k++) {
//                 f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
//             }

//         }

//     }
//     cout << f[1][n] << endl;

// }
#include <functional>
#include<iostream>
#include "algorithm"
#include <cstring>
#include <vector>
#include "queue"
using namespace std;

int n;
int answer;
int main() {
    priority_queue <int , vector<int>,greater<int>> q;
    cin >> n;
    while (n -- ) {
       int x;
       cin >>x;
       q.push(x);
    }
    while(q.size()>1){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        answer += a+b;
        q.push(a+b);
    }
    cout << answer <<endl;





    return 0;
}