Hа кольцевой парковке есть n мест пронумерованых от 1 до n. Есть два вида событий прибытие
машину на парковку и отъезд машины с парковки. Если машина приезжает на парковку, а её место
занято, то она едет далее по кругу и встаёт на первое свободное место.
Формат входного файла:
В первой строке входного файла находится два числа n и m — размер парковки и количество
запросов(1 ≤ n,m ≤ 100000). В следующих m строках находятся события. Каждая из этих строк
имеет следующий вид:
• enter x — приехала машина, которая хочет встать на место x. Для каждой такой команды
выведите какое место займёт эта машина.
• exit x — уехала машина занимавшая место x. Гарантируется, что на этом месте была машина.
Формат выходного файла:
Выведите последовательно результаты выполнения всех операций enter, т.е. какое место займёт вновь прибывшая машина.
Например:
3 5
enter 1
enter 1
exit 1
enter 2
enter 2
Должен выдать:
1
2
3
1
За линейное время делать нельзя (т.е. бежишь, смотришь, где свободно, там и поставлю)
Желательно на С++ или Delphi (сразу лучший ставлю :) ), ну или хотя бы какую структуру данных применить, чтобы это дело реализовать?
Нельзя использовать стандартных библиотек, STL, например.
Примечание:
Ну хотя бы можно описать алгоритмически, как это сделать.
Примечание:
Всё, допилил, Андрей_2009 - AVL - хорошо, но можно лучше, уже запилил через дерево отрезков? но всё равно твой лучший, так что лови....
RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.
Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.
Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.