Codeup 21142: 合并果子（贪心 哈弗曼编码）

题目链接：点击这里

哈夫曼树的构建思想，也就是反复选择两个最小的元素，合并，直到只剩下一个元素。

#include<cstdio>
#include<queue>
using namespace std;

//代表小顶堆的优先队列
priority_queue<long long, vector<long long>, greater<long long> > q;

int main() 
{
	int n;
	long long temp, x, y, ans = 0;
	scanf("%d", &n);
	for(int i = 0; i < n;i++)
	{
		scanf("%lld", &temp);
		q.push(temp); //将初始重量压入优先队列
	}
	
	while(q.size() > 1)	//只要优先队列中至少有两个元素
	{
		x = q.top();
		q.pop();
		y = q.top();
		q.pop();
		q.push(x + y);  //取出堆顶的两个元素，求和后压入优先队列
		ans += x+y;  //累计求和的结果
	}
	printf("%lld\n", ans);  //ans即为消耗的最小体力
	return 0;
}