Bài 15.3. Chiến Dịch Quân Sự - [Độ khó: Khá]

Là chỉ huy tối cao của một quân đội, bạn đang chuẩn bị cho một chiến dịch quân sự quan trọng. Để đảm bảo thành công, bạn cần chọn ra một đội hình gồm ít nhất K binh lính. Tuy nhiên, mỗi binh lính có một "sức mạnh" riêng, và bạn muốn đảm bảo rằng tất cả các binh lính được chọn đều có sức mạnh tối thiểu nhất định để đạt được hiệu quả chiến đấu cao. Bạn cần tìm ngưỡng sức mạnh nhỏ nhất P sao cho có ít nhất K binh lính trong quân đội của bạn có sức mạnh lớn hơn hoặc bằng P.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên N (1 <= N <= 10^5) và K (1 <= K <= N) – lần lượt là tổng số binh lính và số lượng binh lính tối thiểu bạn cần. Dòng thứ hai chứa N số nguyên S_0, S_1, ..., S_{N-1} (1 <= S_i <= 10^9) – sức mạnh của từng binh lính.

OUTPUT FORMAT

In ra số nguyên P – ngưỡng sức mạnh nhỏ nhất thỏa mãn điều kiện.

Ví dụ 1:

Input:

5 3
10 5 20 15 25

Output:

15

Giải thích:

• Có 5 binh lính với sức mạnh: [10, 5, 20, 15, 25]. Bạn cần ít nhất K=3 binh lính.
• Để dễ hình dung, sắp xếp sức mạnh: [5, 10, 15, 20, 25].
• Nếu chọn ngưỡng P=15: có 3 binh lính (15, 20, 25) có sức mạnh >= 15. Điều kiện thỏa mãn.
• Nếu chọn ngưỡng P=16: chỉ có 2 binh lính (20, 25) có sức mạnh >= 16. Điều kiện không thỏa mãn (vì bạn cần ít nhất 3).
• Do đó, ngưỡng sức mạnh nhỏ nhất là 15.

Ví dụ 2:

Input:

4 4
100 90 80 70

Output:

70

Giải thích:

• Có 4 binh lính, sức mạnh: [100, 90, 80, 70]. Bạn cần K=4.
• Ngưỡng P=70: có 4 binh lính (100, 90, 80, 70) có sức mạnh >= 70. Điều kiện thỏa mãn.
• Ngưỡng P=71: chỉ có 3 binh lính (100, 90, 80) có sức mạnh >= 71. Điều kiện không thỏa mãn.
• Ngưỡng nhỏ nhất là 70.