Ліхтарики#513

Ліхтарики (Розбір)

Автор: Андрій Холод

Розробник: Андрій Холод

Розбір підготовано: Костянтин Денисов

Є ліхтариків у точках x_1,\dots,x_n. При радіусі ліхтарик у x_i освітлює відрізок [x_i-r,\;x_i+r]. Потрібно знайти мінімальний , щоб весь відрізок був покритий об'єднанням цих відрізків.

Перевірка для фіксованого радіуса. Відсортуємо координати x_i. Для заданого маємо набір інтервалів [x_i-r,\;x_i+r]; треба перевірити, чи їх об'єднання покриває .

Це робиться жадібно зліва направо. Нехай зараз потрібно покрити точку (спочатку cur=L). Серед усіх інтервалів, що починаються не правіше за (тобто з лівою межею \le cur), візьмемо той, що має найбільшу праву межу, і розширимо покриття до цієї межі. Якщо не існує жодного інтервалу з лівою межею \le cur, то не освітлена і перевірка провалена. Якщо в якийсь момент досягнули cur \ge R, то весь покритий.

Оскільки інтервали впорядковані за x_i, цю перевірку можна зробити одним проходом по масиву.

Як не працювати з дробами. Мінімальний може бути напівцілим, тому зручно масштабувати все вдвічі. Позначимо t=2r (ціле число). Тоді інтервал освітлення в подвоєних координатах має вигляд [2x_i-t,\;2x_i+t], а цільовий відрізок — [2L,\;2R]. Уся перевірка робиться лише цілими числами.

Бінарний пошук відповіді. Якщо для деякого (або ) відрізок покривається, то для будь-якого більшого радіуса теж покривається. Отже, умова монотонна, можна зробити бінарний пошук за .

Беремо межі lo=0, hi=2\cdot 10^9 (цього завжди достатньо для обмежень), і знаходимо мінімальний , для якого перевірка істинна. Після цього відповідь r=\lceil t/2 \rceil, оскільки треба було знайти цілу довжину.

Складність. Сортування O(n\log n). Одна перевірка за фіксованим — . Бінарний пошук по робить близько перевірку, отже сумарно O(n\log n + n\log 10^9), пам'ять .