Mô tả
Chị chủ một gian hàng trên sàn Tiki đang chuẩn bị cho chiến dịch Sale lớn. Gian hàng có sẵn danh sách giá của các sản phẩm đang bán. Để tạo ấn tượng với khách, chị muốn tìm những sản phẩm có giá dao động gần với một mức giá tham chiếu do bộ phận marketing đề xuất, nhằm gom thành một khu vực nổi bật trang chủ. Cụ thể, với mỗi sản phẩm, ta tính độ lệch tuyệt đối giữa giá của nó và giá tham chiếu. Sản phẩm nào có độ lệch nhỏ hơn thì được xem là gần hơn. Nhiệm vụ của bạn là tìm độ lệch tuyệt đối nhỏ thứ k trong toàn bộ danh sách.
Đầu vào
- Dòng đầu chứa hai số nguyên n và k (1 ≤ k ≤ n).
- Dòng thứ hai chứa n số nguyên a₁, a₂, ..., aₙ là giá của từng sản phẩm (|aᵢ| ≤ 10⁶).
- Dòng thứ ba chứa một số nguyên x là giá tham chiếu (|x| ≤ 10⁶).
Đầu ra
- In ra một số nguyên duy nhất là độ lệch tuyệt đối nhỏ thứ k.
Ràng buộc
- 1 ≤ n ≤ 10⁵.
- 1 ≤ k ≤ n.
- Giá trị mỗi phần tử và mức tham chiếu có độ lớn tuyệt đối không vượt quá 10⁶.
Ví dụ
Ví dụ 1: Đầu vào:
5 2 20 30 40 10 50 35
Đầu ra:
10
Giải thích: Giá tham chiếu là 35. Độ lệch của từng sản phẩm lần lượt là |20-35|=15, |30-35|=5, |40-35|=5, |10-35|=25, |50-35|=15. Dãy độ lệch sắp xếp tăng dần là 5, 5, 15, 15, 25. Giá trị nhỏ thứ 2 chính là 5.
Ví dụ 2: Đầu vào:
6 4 12 8 5 20 15 10 10
Đầu ra:
5
Giải thích: Giá tham chiếu là 10. Độ lệch từng sản phẩm là 2, 2, 5, 10, 5, 0. Sắp xếp thành dãy tăng dần: 0, 2, 2, 5, 5, 10. Giá trị nhỏ thứ 4 là 5.