题解 | 哈夫曼编码

# 编码后字符串的长度等于原始的频率乘以编码长度再求和
import heapq
n = int(input())
a = list(map(int, input().split()))
heapq.heapify(a)
total_length = 0
while len(a)>1:
    first = heapq.heappop(a)
    second = heapq.heappop(a)
    combile = first + second
    # 每多一层，编码长度就会+1
    # 那么字符串长度就需要再原来的基础上多一倍原始的频率
    # first和second都需要增加
    # 所以加上combile即可
    total_length += combile
    heapq.heappush(a,combile)
print(total_length)