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

Điểm gần thứ K

Problem code: olpicpc041c10c Group: Uncategorized Points: 2,500 points

View problem

Limits: 1.0 s, 256 MB
AC rate: 21.4%
Solvers: 13

Read the editorial only when you are stuck, and do not copy code from it. Please respect the problem author and the editorialist: submitting an official solution before solving the problem yourself is a bannable offence.

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~.

Comments

You need to sign in to write comments, reply and vote.