题解 | #搬水果#

实质为哈夫曼树
#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;

	}

}