Elearning CodePath – CTP Online Judge

Khoảng cách đặt máy phát

TKM10_BSSTALL

## Đề bài

Trên một trục thẳng có `N` vị trí có thể đặt máy phát sóng. Vị trí thứ `i` có tọa độ `Xi`.

Bạn cần chọn đúng `M` vị trí để đặt máy phát sao cho khoảng cách nhỏ nhất giữa hai máy phát bất kỳ là lớn nhất có thể.

Các tọa độ đầu vào có thể chưa được sắp xếp và có thể có nhiều vị trí trùng tọa độ. Mỗi vị trí trong danh sách chỉ được dùng một lần.

Hãy in ra giá trị lớn nhất của khoảng cách nhỏ nhất đó.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `N` và `M`.
- Dòng thứ hai chứa `N` số nguyên `X1, X2, ..., XN`.

## Dữ liệu ra

In ra một số nguyên duy nhất — khoảng cách nhỏ nhất lớn nhất có thể.

## Ràng buộc

```text
2 <= M <= N <= 200000
0 <= Xi <= 10^9
```

## Subtask

- Subtask 1 — 25 điểm: `N <= 20`, `Xi <= 100`.
- Subtask 2 — 35 điểm: `N <= 5000`, `Xi <= 10^6`.
- Subtask 3 — 40 điểm: Không có ràng buộc bổ sung.

## Ví dụ

### Input

```text
5 3
1 2 8 4 9
```

### Output

```text
3
```

## Giải thích ví dụ

Có thể chọn các vị trí `1, 4, 8`. Khi đó khoảng cách nhỏ nhất là `3`.

Không thể chọn `3` vị trí sao cho mọi khoảng cách liên tiếp đều ít nhất `4`, nên đáp án là `3`.

✅ Đã AC: 0 / 0 submissions