重庆网站设计软件,app运营成本估算,中国产业信息网,开发公司可以注册一造吗问题描述 Huffman树在编码中有着广泛的应用。在这里#xff0c;我们只关心Huffman树的构造过程。 给出一列数{pi}{p0, p1, …, pn-1}#xff0c;用这列数构造Huffman树的过程如下#xff1a; 1. 找到{pi}中最小的两个数#xff0c;设为pa和pb#xff0c;将pa和pb从…问题描述 Huffman树在编码中有着广泛的应用。在这里我们只关心Huffman树的构造过程。 给出一列数{pi}{p0, p1, …, 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构造过程结束总费用为510172759。
输入格式 输入的第一行包含一个正整数nn100。 接下来是n个正整数表示p0, p1, …, pn-1每个数不超过1000。
输出格式 输出用这些数构造Huffman树的总费用。
样例输入
5 5 3 8 2 9
样例输出
59 #includeiostream
#includealgorithm
using namespace std;
int num[110];
int cmp(int a,int b)
{return ab;
}
int main()
{int n,sum0;cinn;int flagn;//flag记录当前集合元素个数 for(int i1;in;i)cinnum[i];while(flag!1)//直到一个为止 {sort(num1,num1flag,cmp);//大到小排列 num[flag-1]num[flag];//最小的两个加起来存在flag-1那个位置 flag--; sumnum[flag];//费用加上 }coutsumendl;}
