题解 | #哈夫曼树#

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;


int main() {
	int n;
	while(scanf("%d",&n) != EOF) {
		//优先队列默认是采用的是大根堆，而哈夫曼树一次选择的是权值较小的两个点，因此需要重新定义优先队列
		priority_queue<int,vector<int>,greater<int>> myPriorityQueue;
		while(n--) {
			int weight;
			scanf("%d",&weight);
			myPriorityQueue.push(weight);
		}
		int wpl = 0;
		while(myPriorityQueue.size() > 1) {
			int a = myPriorityQueue.top();
			myPriorityQueue.pop();
			int b = myPriorityQueue.top();
			myPriorityQueue.pop();
			myPriorityQueue.push(a + b);
			wpl += (a + b);
		}
		printf("%d\n",wpl);
	}
	return 0;
}