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

Biến đổi bài toán: Với 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 khoảng $[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(N.log(N) + Q.log(c).log(N))$ ~O(N.log(N) + Q.log(c).log(N))~ với $c\ge2.10^8$ ~c\ge2.10^8~.

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

Comments