题解 | #哈夫曼树#

//土尔逊Torson 编写于2023/06/12
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		priority_queue<int> myPriorityQueue;
		for (int i = 0; i < n; ++i) {
			int leaf;
			scanf("%d", &leaf);
			myPriorityQueue.push(-leaf);
		}
		int res = 0;//存储带权路径和的中间结果
		while (myPriorityQueue.size() > 1) {
			int leaf1 = myPriorityQueue.top();
			myPriorityQueue.pop();
			int leaf2 = myPriorityQueue.top();
			myPriorityQueue.pop();
			//计算带权路径和
			res = res + leaf1 + leaf2;
			//把构造的新子树插入回原集合K中
			myPriorityQueue.push(leaf1 + leaf2);
		}
		printf("%d\n", -res);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")