一、题目

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，构造结束，费用为5+10+17+27=59.

输入：

输入的第一行包含一个正整数n（n<=100）.

接下来是n个正整数，表示p0，p1,,,pn，每个数不超过1000.

输出：

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

二、例子

输入：

5

5 3 8 2 9

输出：

59

三、涉及的知识

  • map()函数具体讲解：CSDN​​​​​​
  • append()函数具体讲解：CSDN
  • 列表删除元素语法：列表.pop(下标)

例：

mylist = ["rabbit","cat","dog"]mylist.pop(2)print(mylist)

运行结果：

[‘rabbit’, ‘cat’]

  • 列表排序有两种方法：

1.list.sort():就地修改列表，返回None。

例：

mylist = [1,4,5,3,2]mylist.sort()print(mylist)

运行结果：

[1, 2, 3, 4, 5]

2.sorted(列表):返回一个排序的新列表，原列表不变。

mylist = [1,4,5,3,2]sorted(mylist)print(mylist)

运行结果：

[1, 4, 5, 3, 2]

四、python代码及逐行解析

n = int(input())value = 0list = list(map(int,input().split())) #输入的值填入列表for i in range(n - 1):list = sorted(list) #顺序排序value += list[0] + list[1]#最小的两个数相加value_list = list[0] + list[1]#被相加的两个数合并list.pop(0) #删除第一个数list.pop(0) #删除第二个数list.append(value_list) #把合并后的数加到列表中print(value)

运行结果：

4
1 8 3 10
38