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

Cho hai danh sách nums và costs. Mỗi phép toán cho phép tăng hoặc giảm nums[i] với chi phí costs[i]. Tìm chi phí tổng tối thiểu để làm cho tất cả các phần tử trong nums bằng nhau.

Ví dụ

Đầu vào: nums = [3, 2, 4], costs = [1, 10, 2].
Đầu ra: 5 (giảm 3 thành 2 chi phí 1, giảm 4 thành 2 chi phí 2 mỗi lần, tổng 5).

Thuật toán

1. Định nghĩa hàm helper(target) tính tổng chi phí để đưa tất cả phần tử về target.
2. Sử dụng tìm kiếm nhị phân trên khoảng [0, max(nums)] để tìm target tối ưu:
   • Tính mid = (low + high) // 2.
   • Nếu helper(mid) < helper(mid+1), thu hẹp high = mid.
   • Ngược lại, low = mid + 1.
3. Trả về helper(low).

Mã nguồn Python

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 / Đầu ra

Input: [3, 2, 4], [1, 10, 2]
Output: 5