基础练习 Huffuman树 时间限制:1.0s 内存限制:512.0MB 问题描述 Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
给出一列数{p i}={p 0, p 1, …, p n -1},用这列数构造Huffman树的过程如下:
1. 找到{p i}中最小的两个数,设为p a和p b,将p a和p b从{p i}中删除掉,然后将它们的和加入到{p i}中。这个过程的费用记为p a + p b。
2. 重复步骤1,直到{p i}中只剩下一个数。
在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。
本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。
例如,对于数列{p i}={5, 3, 8, 2, 9},Huffman树的构造过程如下:
1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{p i}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。
2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{p i}中删除它们并将和10加入,得到{8, 9, 10},费用为10。
3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{p i}中删除它们并将和17加入,得到{10, 17},费用为17。
4. 找到{10, 17}中最小的两个数,分别是10和17,从{p i}中删除它们并将和27加入,得到{27},费用为27。
5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。 输入格式 输入的第一行包含一个正整数n(n<=100)。
接下来是n个正整数,表示p 0, p 1, …, p n -1,每个数不超过1000。 输出格式 输出用这些数构造Huffman树的总费用。 样例输入 5
5 3 8 2 9 样例输出 59 若果大家学过数据结构或者离散数学,因该对这种算法并不陌生,题目中就是要求计算这棵哈弗曼树的每一个分支点的权值之和,实际上就是这棵树的权,分析可知,这个算法涉及到排序以及集合的相关运算,自然会想到STL中的set,不过,因为集合中可能会出现相同的元素,因此应该使用multiset,数据操作主要有弹出,插入,删除,弹出元素需要使用迭代器,it指向begin()的位置,然后*it获取值,最后erase(it)删除这个元素,每次弹出两个元素,并将这两个元素的和插入到容器中,将两个元素的和累加到sum中去,如果最终容器中只有一个元素,运算停止。
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <memory.h>
using namespace std;
multiset<int> s;
multiset<int>::iterator it;
int sum;
void init()
{
s.clear();
sum=0;
}
void operate()
{
int a,b;
while(s.size()>1)
{
it=s.begin();
a=*it;
s.erase(it++);
b=*it;
s.erase(it);
s.insert(a+b);
sum+=(a+b);
}
it=s.begin();
}
int main()
{
int i,n,num;
cin>>n;
for(i=0;i<n;i++)
{
cin>>num;
s.insert(num);
}
operate();
cout<<sum<<endl;
return 0;
}