题解 | #牛牛算数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 表示有n个数。
# @param c int整型 参数c
# @param a int整型一维数组 ai表示第i个数的大小
# @return long长整型
#
class Solution:
    def solve(self , n , c , a ):
        # write code here
        # 思路：每次取最小的两个数相加
        if len(a) < 2:
            return 0
        if len(a) == 2:
            return c*(sum(a))

        import heapq
        # 初始化最小堆，a内部元素位置调整
        heapq.heapify(a)

        res = []
        # 每一轮取出最小的两个数相加，堆的长度-1，然后更新最小堆
        while len(a) > 2:
            # 弹出堆顶，堆的长度-1，更新最小堆
            a0 = heapq.heappop(a)
            # 记录这一轮求和的值
            tmp = a0 + a[0]
            res.append(tmp)
            # 堆顶用求和值替换，更新最小堆
            heapq.heapreplace(a, tmp)
            
        return c*(sum(res) + a[0] + a[1])