Chia Cặp 2
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(n\) học sinh có năng lực \(a_1\), \(a_2\),..., \(a_n\). Thầy giáo muốn chọn ra \(k\) cặp học sinh rời nhau. Gọi \(x\) là chênh lệch nhỏ nhất giữa hai bạn trong một nhóm. Thầy muốn \(x\) càng lớn càng tốt. Hãy in ra \(\max x\).
Input
-
Dòng đầu có 2 số nguyên \(n, k \ (2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2})\).
-
Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)
Output
- In ra một số nguyên là kết quả bài toán
Example
Test 1
Input
6 2
1 4 3 7 12 9Output
8Note
chúng ta chia cặp như sau: \((1, 9), (3, 12)\). Cặp có khoảng cách nhỏ nhất là \((1, 9)\) và \(9-1=8\).
Test 2
Input
6 1
1 4 3 7 11 9 Output
10Note
chia cặp \((1, 11)\).
Bình luận
This comment is hidden due to too much negative feedback. Click here to view it.