Chương trình tìm tổng chi phí tối thiểu để cân bằng các phần tử danh sách bằng Python

Giả sử chúng ta có hai danh sách các số được gọi là num và chi phí. Bây giờ hãy xem xét, có một hoạt động mà chúng ta có thể tăng hoặc giảm nums [i] cho chi phí giá [i]. Chúng tôi có thể thực hiện bất kỳ số lượng các phép toán này và chúng tôi muốn làm cho tất cả các phần tử bằng nhau về số lượng. Chúng tôi phải tìm tổng chi phí tối thiểu được yêu cầu.

Vì vậy, nếu đầu vào giống như nums =[3, 2, 4] cost =[1, 10, 2], thì đầu ra sẽ là 5, như thể chúng ta có thể giảm số 3 thành 2 với chi phí là 1. Sau đó chúng ta có thể giảm 4 hai lần với chi phí mỗi lần là 2.

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

• Định nghĩa một hàm trợ giúp (). Điều này sẽ đạt được mục tiêu

• tổng:=0

• đối với mỗi i, n trong liệt kê (nums), thực hiện

  • nếu mục tiêu không giống với n, thì

    • tổng:=tổng + | n-target | * chi phí [i]

• tổng trả lại

• Từ phương thức chính, thực hiện như sau:

• thấp:=0, cao:=tối đa là số

• trong khi low

  • giữa:=(thấp + cao) / 2

  • if helper (mid)

    • cao:=giữa

  • nếu không,

    • thấp:=mid + 1

• trả về trình trợ giúp (thấp)

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, costs):
      def helper(target):
         total = 0
         for i,n in enumerate(nums):
            if target != n:
               total += abs(n-target) * costs[i]
         return total
      low,high = 0, max(nums)
      while low < high:
         mid = low + high >> 1
         if helper(mid) < helper (mid+1):
            high = mid
         else:
            low = mid + 1
      return helper(low)
ob = Solution()
nums = [3, 2, 4]
costs = [1, 10, 2]
print(ob.solve(nums, costs))

Đầu vào

[3, 2, 4], [1, 10, 2]

Đầu ra

5