Bố trí trạm phát sóng
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên một trục đường thẳng có $n$ vị trí tiềm năng tại các tọa độ $x_1, x_2, \dots, x_n$. Bạn cần chọn đúng $k$ vị trí để đặt trạm phát sóng sao cho khoảng cách nhỏ nhất giữa hai trạm bất kỳ là lớn nhất có thể.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $n, k$ ($2 \le k \le n \le 10^5$).
- Dòng thứ hai chứa $n$ số nguyên phân biệt $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là khoảng cách nhỏ nhất lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 5 3 1 2 8 4 9 |
3 |
Giới hạn
- $2 \le k \le n \le 10^5, 0 \le x_i \le 10^9$
Community Discussion