Tìm khoảng cách lớn nhất giữa thành phố và trạm gần nhất trong Python

Cho N thành phố (0 đến N-1) và danh sách thành phố có trạm. Tìm khoảng cách lớn nhất từ một thành phố bất kỳ đến trạm gần nhất. Thứ tự trạm cho trước có thể tùy ý.

Ví dụ: N = 6, stations = [2, 4] → Kết quả: 2 (thành phố 0 cách trạm 2 khoảng cách 2, thành phố 5 cách trạm 4 khoảng cách 1).

Thuật toán

1. Tạo mảng station_present đánh dấu thành phố có trạm.
2. Duyệt qua các thành phố, đếm dist = số thành phố liên tiếp không có trạm.
3. Khi gặp trạm: maximum_dist = max(maximum_dist, (dist + 1) // 2), reset dist = 0.
4. Cuối cùng: max(maximum_dist, dist) (xử lý đoạn cuối không có trạm).

Ví dụ code

def get_max_dist(N, station):
    station_present = [False] * N
    for city in station:
        station_present[city] = True
    dist, maximum_dist = 0, min(station)
    for city in range(N):
        if station_present[city]:
            maximum_dist = max((dist + 1) // 2, maximum_dist)
            dist = 0
        else:
            dist += 1
    return max(maximum_dist, dist)

N = 6
station = [2, 4]
print(get_max_dist(N, station))

Input

6, [2, 4]

Output

2