蓝桥杯基础练习 Huffuman树

最新推荐文章于 2022-05-15 01:05:48 发布

林下的码路

最新推荐文章于 2022-05-15 01:05:48 发布

阅读量1k

点赞数

分类专栏：数论贪心蓝桥杯文章标签：算法

本文链接：https://blog.csdn.net/Enjoying_Science/article/details/50602452

版权

贪心同时被 3 个专栏收录

95 篇文章

订阅专栏

数论

79 篇文章

订阅专栏

蓝桥杯

44 篇文章

订阅专栏

Link：http://lx.lanqiao.org/problem.page?gpid=T69

基础练习 Huffuman树

时间限制：1.0s 内存限制：512.0MB

问题描述

　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{ pi}={ p 0, p 1, …, pn -1}，用这列数构造Huffman树的过程如下：
　　1. 找到{ pi}中最小的两个数，设为 pa和 pb，将 pa和 pb从{ pi}中删除掉，然后将它们的和加入到{ pi}中。这个过程的费用记为 pa + pb。
　　2. 重复步骤1，直到{ pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{ pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{ pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{ pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{ pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{ pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入格式

　　输入的第一行包含一个正整数 n（ n<=100）。
　　接下来是 n个正整数，表示 p 0, p 1, …, pn -1，每个数不超过1000。

输出格式

　　输出用这些数构造Huffman树的总费用。

样例输入


 
3 8 2 9 

样例输出

59

编程思想：贪心。

AC code：

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<queue>

using namespace std;

struct node{
	int val;
	bool operator < (const node &a)const
	{
		return val>a.val;
	}
};

int main()
{
//	freopen("D:\\in.txt","r",stdin);
	int n,i,j;
	int a[111];
	priority_queue<node>pq;
	while(scanf("%d",&n)!=EOF)
	{
		node t;
		for(i=0;i<n;i++)
		{
			scanf("%d",&t.val);
			pq.push(t);
		}
		if(pq.size()==1)
		{
			node ans=pq.top();
			pq.pop();
			printf("%d\n",ans.val);
			continue;
		}
		int sum=0;
		while(pq.size()>=2)
		{
			node tmp1=pq.top(); pq.pop();
			node tmp2=pq.top(); pq.pop();
			sum+=(tmp1.val+tmp2.val);
			node tmp;
			tmp.val=tmp1.val+tmp2.val;
			pq.push(tmp);
		}
		printf("%d\n",sum);
	}
	return 0;
}