Chương trình tìm bán kính nhỏ nhất chiếu sáng tất cả nhà trên đường trong Python

Cho danh sách vị trí nhà nums trên đường 1D. Có 3 đèn đường đặt tùy ý, đèn tại x chiếu sáng đoạn [x-r, x+r]. Tìm r nhỏ nhất để chiếu sáng hết nhà.

Ví dụ: nums = [4,5,6,7] → 0.5 (đặt đèn tại 4.5, 5.5, 6.5).

Giải thuật (Binary Search + Kiểm tra tham lam)

1. Sắp xếp nums.
2. Hàm valid(r): đặt đèn đầu tại nums[0] + r, đếm số đèn cần. Nếu ≤ 3 → True.
3. Binary search r trong [0, max(nums)] với 20 lần lặp (độ chính xác float).

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        def valid(r):
            last_location = nums[0] + r
            count = 1
            for val in nums:
                if val - last_location > r:
                    count += 1
                    last_location = val + r
            return count <= 3
        
        nums.sort()
        left, right = 0.0, float(nums[-1])
        res = float('inf')
        for _ in range(20):  # độ chính xác ~ 1e-6
            mid = (left + right) / 2
            if valid(mid):
                res = min(res, mid)
                right = mid
            else:
                left = mid
        return res

ob = Solution()
nums = [4, 5, 6, 7]
print(ob.solve(nums))  # Output: 0.5

Đầu vào / Đầu ra

Input: [4, 5, 6, 7]

Output: 0.5