3.15 进阶 翻译 单词

1.Huffuman树作者: Turbo时间限制: 1s章节: 基本练习数组问题描述Huffman树在编码中有着广泛的应用。在这里我们只关心Huffman树的构造过程。给出一列数{pi}{p0,p1, …,pn-1}用这列数构造Huffman树的过程如下1. 找到{pi}中最小的两个数设为pa和pb将pa和pb从{pi}中删除掉然后将它们的和加入到{pi}中。这个过程的费用记为papb。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树的总费用。代码部分#include bits/stdc.h using namespace std; bool cmp(int a,int b){ return ab; } int main(){ int n; cinn; vectorint list; for(int i0;in;i){ int a; cina; list.push_back(a); } int total0; while(list.size()1){ sort(list.begin(),list.end(),cmp); int alist[0]list[1]; totala; list.erase(list.begin()); list.erase(list.begin()); list.push_back(a); } couttotalendl; return 0; }个人总结思路常见复习1~30简单中等题翻译单词