题解 | #哈夫曼树#

import heapq


class Node:
    def __init__(self, weight):
        self.left = None
        self.right = None
        self.weight = weight

    def __lt__(self, other):
        return self.weight < other.weight


def build_huffman_tree(weights):
    nodes = [Node(w) for w in weights]
    heapq.heapify(nodes)
    while len(nodes) > 1:
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        parent = Node(left.weight + right.weight)
        parent.left = left
        parent.right = right
        heapq.heappush(nodes, parent)
    return nodes[0]


def encode(root, prefix="", encoding={}):
    if root.left is None and root.right is None:
        encoding[root.weight] = prefix
    if root.left:
        encode(root.left, prefix + "0", encoding)
    if root.right:
        encode(root.right, prefix + "1", encoding)
    return encoding


def get_sum(node, depth):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return depth * node.weight
    return get_sum(node.left, depth + 1) + get_sum(node.right, depth + 1)


def huffman_tree(weights):
    root_node = build_huffman_tree(weights)
    encoding = encode(root_node)
    return get_sum(root_node, 0)


while True:
    try:
        n = int(input().strip())
        weights = list(map(int, input().strip().split()))
        print(huffman_tree(weights))
    except:
        break