题解 | 哈夫曼树

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cstring>
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

//哈夫曼树，第一行输入一个数n，表示叶结点的个数。
//需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，
//题目需要输出所有结点的值与权值的乘积之和的最小值。

//输入有多组数据。
//每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

//输出权值。

int main() {
    int n;
    scanf("%d", &n);
    priority_queue<int> arr; //大根堆
    for (int i = 0; i < n; i++) {
        int weight;
        scanf("%d", &weight);
        arr.push(-weight);//小根堆
    }
    int sum = 0;
    while (arr.size() > 1) {
        int left = arr.top();
        arr.pop();
        int right = arr.top();
        arr.pop();
        sum += left + right;
        arr.push(left + right);
    }
    printf("%d\n", -sum);
    return 0;
}