北邮机试 哈夫曼树_csdn北邮哈夫曼

模拟哈夫曼树的总权值的计算过程，不用真的建树。

#include<bits/stdc++.h>
using namespace std;
int n,k,ans=0;
priority_queue<int,vector<int>,greater<int> >q;//设置为小根堆 
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>k;
		q.push(k);
	 } 
	 while(!q.empty())
	 {
	 	int a=q.top();q.pop();
	 	int b=q.top();q.pop();
	 	if(q.empty())
	 	{
	 		ans=ans+a+b;
	 		cout<<ans<<endl;
	        return 0;
		 }
	 	ans=ans+a+b;//a+b是一个节点 
	 	q.push(a+b);
	 }
	cout<<ans<<endl;
	return 0;
}
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