3015 - 【设计型】第11章：指针和数组 Huffuman树（2）
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。
<span style="font-family:宋体, 'Times New Roman';font-size:14px;line-height:22px;background-color:#E4F1FF;"> 5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。</span>
<span style="font-size:14px;line-height:22px;background-color:#E4F1FF;"><strong>注：该过程每次不只删去两个数，如最小的两个数值为5,10；并且在数组中有3个元素分别为5,10，10，那么同时删掉这三个元素，并将25加入数组。如果数组为5,5,10,10，则首先将两个5删掉，将10插入数组中，之后同时删掉3个10，并将30加入数组中。</strong></span>
Input
输入的第一行包含一个正整数n。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
Output
输出用这些数构造Huffman树的总费用。
Examples
Input
5 5 3 8 2 9
Output
59
Solution C++
#include<iostream> using namespace std; int sum = 0; int main() { int N; cin >> N; int *num = new int[N]; for(int i = 0; i < N; i++) { cin >> num[i]; } int min = 0; int min_d = 0; int min_mid = 0; int min_dmid = 0; for(int count = N; count > 1; count--) { min_mid = 0; min_dmid = 0; for(int i = 0; i < N; i++) { if((num[i] != 0) && (num[i] < num[min])) { min = i; } } //令mid_d为不等于min的一个值，排除num[min]后求剩下的元素最小值 for(int i = 0; i < N; i++) { if((num[i] != 0) && (i != min)) { min_d = i; break; } } for(int i = 0; i < N; i++) { if(i == min) continue; else { if((num[i] != 0) && (num[i] < num[min_d])) { min_d = i; } } } min_dmid = num[min_d];//因为相加后就得将改坐标删除，所以用两个中间变量记录两个最小值 min_mid = num[min]; for(int i = 0; i < N; i++) { if((num[i] != 0) && (num[i] == min_dmid)) { sum += min_dmid; num[i] = 0; } if((num[i] != 0) && (num[i] == min_mid) && (min_mid != min_dmid)) { sum += min_mid; num[i] = 0; } } num[min] = min_mid + min_dmid; } cout << sum << endl; delete [] num; return 0; }