Editorial for Chênh lệch nhỏ nhất

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

Tiến hành sắp xếp mảng $a$ ~a~ tăng dần. Với mỗi truy vấn, tìm chỉ số nhỏ nhất thỏa mãn giá trị phần tử lớn hơn hoặc bằng $x$ ~x~ thông qua Tìm kiếm nhị phân (có thể sử dụng hàm lower_bound), gọi chỉ số đó là $i$ ~i~. Khi đó, chỉ số lớn nhất thỏa mãn giá trị phần tử nhỏ hơn $x$ ~x~ là $i-1$ ~i-1~.

Đáp án bài toán là độ chênh lệch giữa $x$ ~x~ với một trong hai phần tử tại chỉ số $i$ ~i~ hoặc $i-1$ ~i-1~. $answer=min\{|x-a_i|,|x-a_{i-1}|\}$ ~answer=min\{|x-a_i|,|x-a_{i-1}|\}~.

Độ phức tạp: $O(n.log(n)+q.log(n))$ ~O(n.log(n)+q.log(n))~.

Editorial for Chênh lệch nhỏ nhất

Comments