UniLecs #Task. Очередь
Задача: в больнице большие очереди к врачам, т.к. врачей не хватает. Обычные граждане встают в конец очереди, а пенсионеры встают ровно в ее середину (при нечетной длине очереди, они встают сразу за центром, т.е. при 5 встают за 3м).
Вам необходимо написать программу для табло электронной очереди.
Примечание: врачей в больнице так мало, что гарантируется, что очередь никогда не пуста.
Входные данные: дан список команд в следующем формате:
- “+ {i}” — гражданин с номером i встал в конец очереди.
- “* {i}” — пенсионер с номером i встал в середину очереди.
- “-” — первый гражданин в очереди зашел к врачу.
Вывод: для каждого запроса формата “-” табло должно вывести номер гражданина, который должен зайти к врачу.
Пример:
1. [ “+1”, “+2”, “-”, “+3”, “+4”, “-”, “-” ]
Output: 1 2 3
2. [ “+1”, “+2”, “*3”, “-”, “+4”, “*5”, “-”, “-”, “-”, “-” ]
Output: 1 3 2 5 4
Разбор
Разобьем очередь на две части пополам. Размер первой части всегда должен быть равен размеру 2й части, или быть на 1 больше. Необходимо всегда поддерживать это свойство.
Тогда добавление гражданина в конец очереди — это добавление его в конец второй части, добавление пенсионера — это добавление его в начало второй части, а удаление гражданина из очереди — это удаление его из начала первой части.
После каждой операции необходимо выполнить “балансировку”, поддерживая необходимые требования к двум частям. Если в первой части элементов оказалось меньше, чем во второй, то нужно первый элемент из второй части добавить в конец первой части.
Реализация
C#
https://gist.github.com/unilecs/2d2760aa23d24f1ae6f997cd2f134259
C++
https://gist.github.com/unilecs/a72dd84935f8f719ee1b79f029ee8d5d
Python
https://gist.github.com/unilecs/73bd7539afc66cece848f2b4ad6c770e
