CS
Задачник Базовый курс EN

Задача

Заказы по сроку

куча хеш-таблица расписание собеседования

В службу доставки приходят заказы, у каждого — срок, к которому его нужно выполнить (целое число, например номер минуты). Сроки у разных заказов могут совпадать. Диспетчеру нужны четыре операции:

  • + d — пришёл заказ со сроком d;
  • - d — отменили один заказ со сроком d; если таких заказов нет, ничего не происходит;
  • ? d — есть ли сейчас хотя бы один заказ со сроком d;
  • min — самый ранний срок среди заказов, которые сейчас ждут.

Обработайте журнал операций.

Вход

В первой строке q (1 ≤ q ≤ 2·10⁵). Дальше q строк с операциями; 0 ≤ d ≤ 10⁹.

Выход

На каждую операцию ? — строка yes или no, на каждую min — самый ранний срок или -, если заказов нет.

Примеры

Пример 1

Вход
13
+ 20
+ 5
+ 5
min
- 5
? 5
min
- 5
? 5
min
- 7
- 20
min
Выход
5
yes
5
no
20
-

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Каждой операции нужна своя структура. Какая отвечает «есть ли такой срок» за O(1), а какая — «самый ранний» за O(log n)? Можно ли держать обе сразу?

2Идея

Словарь «срок → сколько заказов с ним» отвечает на ? и обрабатывает отмену за O(1). Двоичная куча сроков отвечает на min, но удалять из середины кучи дорого. Поэтому отмена кучу не трогает: в ней остаются устаревшие записи. Когда спрашивают минимум, с вершины кучи выбрасываются сроки, которых по словарю уже нет, — это ленивое удаление.

3Разбор

Почему это быстро: каждый добавленный срок попадает в кучу один раз и выбрасывается из неё не больше одного раза, поэтому все выбрасывания вместе стоят O(q log q), как бы они ни распределились по запросам. Словарь при этом всегда точен, и куча нужна только для порядка. Одинаковые сроки обрабатываются сами: в куче несколько записей с одним сроком, в словаре — их число, и запись выбрасывается, только когда число стало нулём.

Решение на одном списке верно, но in, remove и min проходят весь список. В пятом тесте одновременно ждут десятки тысяч заказов, и каждая из 150 тысяч операций стоит десятки тысяч шагов. Какая структура для какой операции и сколько каждая стоит на замере — в статье «Как выбрать структуру данных».

3+Решение
4Сложность

O(q log q) по времени и O(q) по памяти: куча может хранить и отменённые сроки, но не больше, чем их было добавлено.

5Типичные ошибки
  • Один список. Верно, но O(q) на операцию.
  • Множество вместо счётчика. Два заказа со сроком 5, отменили один — срок 5 должен остаться. Пример это проверяет.
  • Отмена несуществующего. Счётчик не должен уходить в минус: иначе следующий заказ с этим сроком окажется «невидимым».

Алгоритмы задачи

TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи
Каталог алгоритмов