题目大意

可以合并两堆果子成一堆新果子，消耗两堆果子数目之和的体力。给定 $n$ 堆果子的数目 $a_i$，求体力耗费最小的方案。

分析

很容易猜到贪心结论，不断选取两个最小的堆进行合并。

priority_queue<int, vector<int>, greater<int> > q;

int main() {
	int n = rr();
	for (ll i = 1; i <= n; i++) {
		int t = rr();
		q.push(t);
	}
	int sum = 0;
	while (q.size() >= 2) {
		int x = q.top(); q.pop();
		int y = q.top(); q.pop();
		sum += x + y;
		q.push(x + y);
	}
	printf("%d\n", sum);
	return 0;
}

本质上是证明 Huffman 树的构造的正确性，有点复杂。