Codeforces 100971.D

Ссылка на задачу

• Codeforces #100971.D — Прокладка кабелей

Комментарии

Пусть город-родитель может располагаться только справа.

Отсортируем города по возрастанию координаты, а также заведём стек городов. Будем идти по городам слева направо. Пусть C — город на вершине стека, R — текущий просматриваемый город. Пока население C меньше населения R, снимаем C со стека и говорим, что R — родитель C. После завершения цикла while кладём R в стек.

Пусть теперь город-родитель также может располагаться слева.

Делаем то же самое, но идём по городам слева направо. Пусть C — город на вершине стека, L — текущий просматриваемый город, R — найденный на предыдущем этапе правый родитель C (если он есть). Пока население C меньше населения L, снимаем C со стека; если при этом R == -1, либо расстояние от C до L меньше расстояния от C до R, либо расстояния равны, но население L больше населения R, то говорим, что L — родитель C. После завершения цикла while кладём L в стек.