Thi thử Tuyển sinh Lớp 10 Chuyên Tin Hải Phòng năm 2026

Nov 14, 2026, 19:00 – 18:59 (02:30:00) Live
Time Remaining 364 days 21:44:10
My Score
0 / 500
Rank
- / 2

E. Bài 5. Trạm nghỉ

100 points 1.0 s 256 MB binary-search greedy

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.

Sample Test 1
AC 3 ms 1.2 MB
Sample Test 2
AC 2 ms 1.1 MB
Sample Test 3
AC 3 ms 1.3 MB