UniLecs #Task. The Great Lainland Migration
Задача: Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются N городов, последовательно пронумерованных от 0 до N−1. Направление в сторону от нулевого города к первому названо восточным, а обратное — западным.
Когда в Лайнландии неожиданно начался кризис, все жители мира стали испытывать глубокое смятение. По всей Лайнландии поползли слухи, что на востоке живётся лучше, чем на западе. Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.
Входные данные: в первой строке дано одно число N (2 ⩽ N ⩽ 10⁵ ) — количество городов в Лайнландии. Во второй строке дано N чисел a(i) ( 0 ⩽a(i)⩽ 10⁹ ) — средняя цена проживания в городах с нулевого по (N− 1)-ый соответственно.
Вывод: для каждого города в порядке с нулевого по (N−1)-й выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите -1.
Пример:
10
1 2 3 2 1 4 2 5 3 1
Output: 1 4 3 4 -1 6 9 8 9 -1
Разбор
Рассмотрим пример из условия. Будем двигаться по городам слева направо. Жители городов, в которых стоимость жизни равна 1, 2, 3 отправляются в путь направо. После этого они встречают город, в котором стоимость жизни равна 2, и в этом городе остаются жители города, где стоимость жизни была равна 3. Но жители города со стоимостью 2 отправляются в путь, поэтому сейчас в пути будут жители городов, где стоимость жизни равна 1, 2, 2. Затем они встречают город, где стоимость жизни равна 1. В нем остаются жители городов, где стоимость жизни была 2 (два города), далее в путь направо идут жители двух городов, где стоимость жизни равна 1.
То есть в очередном встреченном городе остаются все жители левых городов, где стоимость жизни была выше (если они продолжали путь, то есть не остановились раньше), а жители текущего города добавляются к тем, кто движется вправо.
Для решения задачи удобно использовать стек, в который будем хранить стоимость жизни в тех городах, жители которых сейчас находятся в пути. При встрече нового города (пусть стоимость жизни в нем равна cost) из стека удаляются все верхние значения, которые больше cost — жители этих городов остаются в этом городе. Затем число cost добавляется в стек. Таким образом, в стеке всегда хранятся числа в порядке неубывания (наибольшее значение наверху стека).
На самом деле понадобится два стека, в одном стеке хранятся стоимости жизни (costs), в другом стеке хранятся номера городов (nums). Эти номера городов нужны для восстановления ответа — когда из стека costs удаляется стоимость жизни в каком-то городе, из стека nums удаляется номер этого города, при этом нужно в специальном массиве ans сделать пометку, что для данного удаленного города стал известен ответ (текущий номер города).
Удобно также в два имеющихся стека добавить числа, равные -1, чтобы не проверять стеки на пустоту при каждом обращении к верхнему элементу.
Реализация
https://gist.github.com/unilecs/09d4723545ffe3f1cd0e6202ab44456e
