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

Giả sử chúng ta có một danh sách các số được gọi là nums. Chúng ta có thể giảm độ dài của num bằng cách lấy hai số bất kỳ, loại bỏ chúng và thêm tổng của chúng vào cuối. Chi phí thực hiện thao tác này là tổng của hai số nguyên mà chúng tôi đã loại bỏ. Chúng tôi phải tìm tổng chi phí tối thiểu để giảm số xuống một số nguyên.

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 5, 6], thì đầu ra sẽ là 45, vì chúng ta lấy 2 và 3 rồi loại bỏ để nhận được [4, 5, 6, 5], thì chúng ta lấy 4 và 5 sau đó loại bỏ để được [6, 5, 9], sau đó lấy 6 và 5, sau đó loại bỏ chúng và chúng ta được [9, 11], và cuối cùng loại bỏ 9 và 11, chúng ta sẽ nhận được 19. Vậy tổng là 45.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một đống bằng cách sử dụng các phần tử có trong nums
• ans:=0
• trong khi kích thước của nums> =2, thực hiện
  • a:=phần tử cao nhất của số đống
  • b:=phần tử trên cùng của số đống
  • ans:=ans + a + b
  • chèn a + b vào heap nums
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[2, 3, 4, 5, 6]

Đầu ra

45