Editorial for Trạm phát sóng

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 Tìm kiếm nhị phân (Binary Search) cho đáp án bài toán. Với mỗi khoảng cách $r$ ~r~, cần kiểm tra mỗi thành phố phải được bao phủ bởi ít nhất một trạm phát sóng.

Tiến hành sắp xếp tọa độ các trạm phát sóng. Để kiểm tra khoảng cách $r$ ~r~ là thỏa mãn, mỗi thành phố $i$ ~i~ $(1 \le i \le n)$ ~(1 \le i \le n)~ được phủ sóng nếu có ít nhất một trạm phát sóng trong khoảng tọa độ $[c_i-r,c_i+r]$ ~[c_i-r,c_i+r]~ (có thể xử lý bằng Tìm kiếm nhị phân).

Độ phức tạp: $O(n.log(m).log(x))$ ~O(n.log(m).log(x))~ với $x\ge2.10^9$ ~x\ge2.10^9~.

Editorial for Trạm phát sóng

Comments