题解 | #哈夫曼树#

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n, wpl = 0; // wpl 记录最小带权路径长度
    cin >> n;
    vector<int> weight(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    do {
        sort(weight.begin(), weight.end()); // 按权值由小到大调整weight数组
        int temp = weight[0] + weight[1];
        weight.push_back(temp);
        wpl += temp;
        weight.erase(weight.begin(), weight.begin() + 2);
    } while (weight.size() > 1);
    // 遍历调试
    // for(auto i : weight){
    //     cout << i << " ";
    // }
    cout << wpl << endl;
    return 0;
}