Chương trình tìm chi phí tối thiểu để gộp danh sách thành một số nguyên bằng Python

Cho danh sách nums. Mỗi phép toán lấy hai số, xóa chúng, thêm tổng của chúng vào cuối. Chi phí phép toán là tổng hai số bị xóa. Tìm chi phí tối thiểu để gộp danh sách thành một số.

Ví dụ: [2, 3, 4, 5, 6] → 45 (gộp 2+3=5, 4+5=9, 6+5=11, 9+11=20, tổng chi phí = 5+9+11+20=45).

Quy trình giải quyết (Min Heap / Huffman coding)

1. Chuyển nums thành min-heap.
2. Khởi tạo ans = 0.
3. Trong khi kích thước heap ≥ 2:
   • Lấy hai phần tử nhỏ nhất a, b.
   • ans += a + b.
   • Đẩy a + b trở lại heap.
4. Trả về ans.

Ví dụ mã nguồn

class Solution:
    def solve(self, nums):
        import heapq
        heapq.heapify(nums)
        ans = 0
        while len(nums) >= 2:
            a = heapq.heappop(nums)
            b = heapq.heappop(nums)
            ans += a + b
            heapq.heappush(nums, a + b)
        return ans

ob = Solution()
nums = [2, 3, 4, 5, 6]
print(ob.solve(nums))  # Output: 45

Đầu vào

[2, 3, 4, 5, 6]

Đầu ra

45