Bố trí trạm phát sóng

Buổi 73-74 — Virtual CF greedy
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved