https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_928 2026-06-02T22:10:27Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_928&diff=2144&oldid=prev 2016-11-02T17:48:51Z

<p>Новая страница: «== Ссылки на задачу == * [http://acmp.ru/?main=task&amp;id_task=928 ACMP #928 — Берёзовая аллея] == Похожие задачи == …»</p> <p><b>Новая страница</b></p><div>== Ссылки на задачу ==<br /> * [http://acmp.ru/?main=task&amp;id_task=928 ACMP #928 &amp;mdash; Берёзовая аллея]<br /> <br /> == Похожие задачи ==<br /> * [[РОИ 2012-2013, региональный этап, D]]<br /> <br /> == Комментарии ==<br /> Будем перебирать пары (i1, j1) в порядке увеличения суммы (i1 + j1), а при равных суммах – в порядке возрастания i1. Для каждой такой суммы с ростом i1 оба конца отрезка допустимых (для данного i1) значений j2 будут уменьшаться.<br /> <br /> Тогда для хранения этого отрезка можно использовать очередь с поддержкой операций добавления в конец, удаления из начала и поиска минимум за O(1). В этом случае нам потребуется лишь линейная дополнительная память для хранения очереди, длина которой<br /> в каждый момент времени не будет превосходить N.<br /> <br /> [[Category: Сборник задач: ACMP]]<br /> [[Category: Задачи: Очередь]]<br /> [[Category: Задачи: Бинарный поиск]]</div>

Ctrlalt