1.题目

大概：合并一堆质量不同的果子，使得树的带权路径长度WPL最小。
输入
包括两行，第一行是一个整数n（1 <= n <= 300000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 100000）是第i种果子的数目。
3
1 2 9

输出
包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于263。
15

2.思路

哈夫曼树的构建思想：反复选择2个最小的元素，合并，直到只剩下一个元素。
一般可使用优先队列（其实就是堆结构）。
初始将果堆的质量压入优先队列即priority_queue（此处为小顶堆），之后每次从优先队列顶部取出2个最小的数，将它们相加并重新压入优先队列（需要在外部定义一个变量ans，将相加的结果累加），重复直到优先队列只剩下一个数——得到消耗的最小体力ans。

注意：使用priority_queue的greater参数则要加上头文件< functional>，但如果第三个参数是less则不用加这个头文件，另外并且注意第三个参数> >之间有个空格。

3.完整代码

#include<cstdio>
#include<queue>
#include<iostream>
#include<functional>
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){//只要优先队列中至少有2个元素
		x=q.top();
		q.pop();
		y=q.top();
		q.pop();
		q.push(x+y);//取出堆顶的2个元素，求和后压入优先队列
		ans+=(x+y);//累计求和的结果
	}
	printf("%lld\n",ans);//ans为消耗的最小体力
	system("pause");
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

4.类似题目

2012年上机题目（https://blog.csdn.net/qq_38277212/article/details/105345075）

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112797374