https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=Codeforces_100971.D 2026-06-02T22:10:22Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=Codeforces_100971.D&diff=2026&oldid=prev 2016-06-08T13:41:30Z

<p>Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/D Codeforces #100971.D — Прокладка кабелей] == Комме…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://codeforces.com/gym/100971/problem/D Codeforces #100971.D &amp;mdash; Прокладка кабелей]<br /> <br /> == Комментарии ==<br /> Пусть город-родитель может располагаться только справа.<br /> <br /> Отсортируем города по возрастанию координаты, а также заведём стек городов. Будем идти по городам слева направо. Пусть C &amp;mdash; город на вершине стека, R &amp;mdash; текущий просматриваемый город. Пока население C меньше населения R, снимаем C со стека и говорим, что R &amp;mdash; родитель C. После завершения цикла while кладём R в стек.<br /> <br /> Пусть теперь город-родитель также может располагаться слева.<br /> <br /> Делаем то же самое, но идём по городам слева направо. Пусть C &amp;mdash; город на вершине стека, L &amp;mdash; текущий просматриваемый город, R &amp;mdash; найденный на предыдущем этапе правый родитель C (если он есть). Пока население C меньше населения L, снимаем C со стека; если при этом R == -1, либо расстояние от C до L меньше расстояния от C до R, либо расстояния равны, но население L больше населения R, то говорим, что L &amp;mdash; родитель C. После завершения цикла while кладём L в стек.<br /> <br /> [[Category: Сборник задач: Codeforces]]<br /> [[Category: Задачи: Сортировка]]<br /> [[Category: Задачи: Стек]]</div>

Ctrlalt