Chương trình tối đa hóa lực hút tối thiểu giữa các quả bóng trong thùng trong Python

Cho mảng pos vị trí các thùng trên đường thẳng và x quả bóng. Lực giữa 2 bóng tại p, q là |p-q|. Đặt x bóng vào các vị trí trong pos để tối đa hóa lực hút tối thiểu giữa 2 bóng bất kỳ.

Ví dụ: pos=[2,4,6,8,10,12], x=3 → 4. Đặt tại 4,8,12 → lực min = 4.

Giải thuật (Binary Search + Tham lam)

1. Sắp xếp pos.
2. Hàm ball_count(d): số bóng đặt được nếu lực min ≥ d (tham lam: đặt bóng đầu tại pos[0], các bóng sau tại vị trí đầu tiên ≥ curr + d).
3. Binary search left=0, right=pos[-1]-pos[0]:
   • mid = right - (right-left)//2 (upper mid).
   • Nếu ball_count(mid) >= x: left = mid; ngược lại: right = mid-1.
4. Trả về left.

Ví dụ minh họa

def solve(pos, x):
    n = len(pos)
    pos.sort()
    def ball_count(d):
        ans, curr = 1, pos[0]
        for i in range(1, n):
            if pos[i] - curr >= d:
                ans += 1
                curr = pos[i]
        return ans
    left, right = 0, pos[-1] - pos[0]
    while left < right:
        mid = right - (right - left) // 2
        if ball_count(mid) >= x:
            left = mid
        else:
            right = mid - 1
    return left

print(solve([2, 4, 6, 8, 10, 12], 3))

Đầu vào

[2, 4, 6, 8, 10, 12], 3

Đầu ra

4