Bài 5. Trạm nghỉ
Points
100
AC Rate
100.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Trên một tuyến đường cao tốc có $n$ vị trí có thể xây dựng trạm nghỉ, vị trí thứ $i$ nằm tại tọa độ $a_i$ trên trục đường thẳng. Do hạn chế về kinh phí, ban quản lý quyết định loại bỏ đúng $k$ vị trí và chỉ giữ lại các vị trí còn lại để xây trạm nghỉ.
Yêu cầu
Sau khi loại bỏ $k$ vị trí, khoảng cách nhỏ nhất giữa hai trạm nghỉ bất kỳ còn lại phải lớn nhất có thể. Hãy tìm giá trị đó.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên dương $n, k$ ($k \le n - 2$).
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai trạm nghỉ bất kỳ còn lại.
Giới hạn & Subtasks
- Subtask 1 (20% số điểm): $n \le 20, k = 1$.
- Subtask 2 (30% số điểm): $20 < n \le 100$.
- Subtask 3 (25% số điểm): $100 < n \le 2000$.
- Subtask 4 (25% số điểm): $2000 < n \le 10^5$.
- Thời gian chạy tối đa: 1.0 giây.
- Giới hạn bộ nhớ: 256 MB.
Sample Input 1
5 1
4 1 2 3 9
Sample Output 1
1
Giải thích: Xóa $1$ phần tử bất kỳ, thì dãy còn lại luôn tồn tại $2$ số tự nhiên liên tiếp nhau, nên độ chênh lệch nhỏ nhất là $1$.
Sample Input 2
5 2
10 -5 3 -2 1
Sample Output 2
7
Giải thích: Trong các cách xóa $2$ phần tử bất kỳ, cách xóa chỉ còn $3$ phần tử $(10, -5, 3)$ sẽ có độ chênh lệch nhỏ nhất là $7$. Cách xóa này là cách xóa có độ chênh lệch nhỏ nhất giữa các phần tử là lớn nhất.
Community Discussion