Разбор задачи “Автобус характеров”

В недавней статье мы рассматривали такую структура данных как стек. Если вы не знаете что такое стек, то обязательно перейдите по ссылке и почитайте, потому что сегодня мы разберем решение одной интересной задачи с сайта codeforces.com с использованием реализованного ранее нами стека. Вот условие задачи:

В автобусе характеров есть n рядов сидений, в каждом по 2 места. В -м ряду ширина обоих сидений равна сантиметров. Все числа i различны.

Изначально автобус пустой. На каждой из 2n остановок в автобус садится ровно один человек одного из двух характеров:

  • интроверт всегда выбирает ряд, где оба места свободны, при этом из таких рядов он выбирает ряд с самыми узкими сидениями, и занимает одно место;
  • экстраверт всегда выбирает ряд, где уже сидит один человек (интроверт), при этом из таких рядов он выбирает ряд с самыми широкими сидениями, и занимает оставшееся в выбранном ряду место.

Вам дана ширина сидений в каждом ряду, а также порядок, в котором входили пассажиры. Определите, на какой ряд сядет каждый из пассажиров.

Входные данные

В первой строке следует целое число n () — количество рядов сидений в автобусе.

Во второй строке следует последовательность целых чисел (, где равно ширине каждого из двух сидений в -м ряду. Гарантируется, что все различны.

В третьей строке следует строка длины 2n, состоящая из символов «0» и «1» — описание порядка, в котором пассажиры заходят в автобус. Если -й символ строки равен «0», то на -й остановке в автобус зашел интроверт. Если -й символ строки равен «1», то на -й остановке в автобус зашел экстраверт. Гарантируется, что интровертов и экстравертов, которые зашли в автобус, поровну (то есть по n), и для каждого экстраверта всегда найдется подходящий ряд.

Выходные данные

Выведите n целых чисел — номера рядов, в которые сели пассажиры. Номера рядов для пассажиров должны быть выведены в том же порядке, в котором пассажиры заданы во входных данных.

Примеры
входные данные

выходные данные

Описание алгоритма решения задачи

Из условия задачи можно заметить следующую закономерность: каждый новый экстраверт сядет к интроверту, который сидит на сиденье с самой большой шириной. Значит, что могут быть еще интроверты в автобусе, и гарантировано что ширина их сидений меньше. Это типичный стек. Идея для решения в следующем. Пойдем по порядку входных данных. Сначала мы получаем число n и создаем объект класса Stack. Далее ширины сидений мы запишем в map по принципу (номер ряда -> ширина). Затем нам необходимо отсортировать ее (мапу) по значению и последовательно сложить в стек номера рядов, причем на самом верху будет номер с наименьшей шириной. Последовательность из 0 и 1 (интровертов и экстравертов, которые будут заходить в автобус мы  сложим в массив. Рассмотрим пример, в котором n=3, ширины рядов: 8 4 5, а последовательность людей: 0 0 1 1 0 1. Предложенная раскладка данных будет выглядеть так:

Стек номеров рядов, отсортированный по ширине

Последовательность захода людей в автобус

Отлично. Теперь нам необходимо создать второй стек, который будет тоже иметь размерность n, но будет пустым. После мы начинаем последовательно извлекать из массива людей (элементы 0 и 1) и проводить два типа операций в зависимости от того, кто зашел интроверт или экстраверт:

    • Зашел интроверт 0.  Так как зашел интроверт и нам известно, что он сядет на свободный ряд с самой минимальной шириной. Значит мы выводим на консоль и извлекаем элемент из стека с ширинами, и кладем его в пустой, заранее подготовленный стек.

    • Зашел экстраверт 1. Экстраверт сядет к интроверту, причем к тому, который сидит на максимально широком ряду. Из второго стека, мы извлекаем элемент и выводим его на консоль. Это справедливо, потому что если заходили интроверты, то ряд с максимальной шириной окажется на верху стека. Соответственно, если зайдет еще один экстраверт, то он так же сядет с интровертом, у которого ширина ряда максимальная в силу принципа работы нашего стека.


    Реализация алгоритма на языке Java представлена ниже:

Оставить комментарий:

Ваш email не будет опубликован.