AcWing 148 合并果子 题解 (贪心—Huffman树)

思路:按照树的思想考虑合并,树的最底层进行合并时需要计算的次数最多,所以质量最小的两个果子应该在树的最底层,最终所有果子合并到树的根节点,根节点的值即为消耗的体力和。将所有果子质量存入堆中(实现排序),每次挑出质量最小的两堆果子(堆顶的两个元素)合并,将总体力数加上这两堆果子的质量,将新合并成的果子堆的质量存入堆中(作为新的树的节点),这样就能实现合并消耗的总体力最小

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int main()
{
	int n;
	priority_queue<int , vector<int>, greater<int>>heap;//用优先队列实现对所有果子的质量排序的操作 
	
	cin>>n;
	while(n -- ){
		int a;
		cin>>a;
		heap.push(a);
	}
	
	int res = 0;//记录答案
	while(heap.size() > 1){//当树的节点数大于1,代表果子还没合并完 
		//取出当前最小的两个果子 
		int a = heap.top(); heap.pop();
		int b = heap.top(); heap.pop();
		res += a + b;//合并消耗的体力加上a和b的质量 
		heap.push(a + b);//将这两个果子合并,合并后的质量和作为新的节点加入树上 
	} 
	
	cout<<res<<endl; 
	return 0; 
}
上一篇:PromiseA+规范(学习笔记)


下一篇:centos7 配置IPV6