Editorial for Điểm gần thứ K

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Ta có thể biến đổi bài toán như sau: Cho hai số nguyên $B$ ~B~ và $K$ ~K~, tìm giá trị $X$ ~X~ nhỏ nhất thỏa mãn có ít nhất $K$ ~K~ phần tử của dãy $A$ ~A~ có giá trị nằm trong đoạn $[B-X,B+X]$ ~[B-X,B+X]~. Từ đó, tiến hành sắp xếp mảng $A$ ~A~ và thực hiện Tìm kiếm nhị phân với mỗi truy vấn.

Độ phức tạp: $O(Nlog(N)+Qlog(c)log(N))$ ~O(Nlog(N)+Qlog(c)log(N))~

Editorial for Điểm gần thứ K

Comments