题解 | #哈夫曼树#

关键在于找到求解最短路径长度的规律，无需建树
#include <iostream>
#include <queue>
using namespace std;

struct hafuman {
	int value;

};

bool operator < (hafuman lhs, hafuman rhs) {
	return lhs.value > rhs.value;   //变成小根堆

}


int main() {
	int n,dot;
	while (cin >> n) {
		int a, b, res = 0 ; //res表示带权路径长度
		priority_queue<hafuman>  HafumanTree;
		for (int i = 0; i < n; i++) {
			cin >> dot;
			hafuman c;
			c.value = dot;
			HafumanTree.push(c);  //传入小根堆
		}
		while (!HafumanTree.empty()) {
			a = HafumanTree.top().value;
			HafumanTree.pop();
			if (HafumanTree.empty()) break;
			b = HafumanTree.top().value;
			HafumanTree.pop();
			hafuman c;
			c.value = a + b;
			HafumanTree.push(c);
			res = res + a + b;


		}
		cout << res << endl;

	}

}