10167. Студенческая очередь в столовую
В ADA университете студенты
очень любят соревнования по программированию, поэтому каждый студент входит в
одну (и только одну) команду. Но правила разных соревнований разные, и не
всегда одна команда состоит из 3 человек, как по правилам ACM. В любой команде
может быть любое количество студентов (но конечно более 0).
Студенты любят приходить в
свою столовую, которая находится в корпусе C, и проводить свободное время за
чашкой кофе. Студенты в ADA очень умные, не хотят стоять в стандартной очереди
за вкусным кофе. Они решили установить некоторые правила, которым будут
следовать только они.
Когда студент становится в
очередь, он сначала просматривает очередь с начала до конца, чтобы проверить,
находятся ли уже в очереди некоторые из его товарищей по команде (студенты из
его же команды). Если да, то он встает в очередь сразу за ними (позади всех
своих товарищей по команде). В противном случае он становится в конец очереди и
становится новым последним элементом (невезение). Удаление из очереди
выполняется как и в обычных очередях: студенты обрабатываются с начала до конца
в том же порядке, в котором они стоят в очереди.
Вам следует написать
программу, имитирующую такую очередь.
Вход. Первая строка содержит количество команд t (1 ≤ t ≤ 1000). Каждая из следующих t строк описывает одну команду. Первый элемент в строке – это
количество n (1 ≤ n ≤ 1000) студентов в
команде. Далее в строке следуют n целых
чисел, задающих идентификаторы (0 ≤ ID ≤ 106)
учащихся в одной команде.
Далее следует список команд.
Имеется два разных типа команд:
·
ENQUEUE x –
студент x становится в
очередь;
·
DEQUEUE – обработка первого студента в очереди и
удаление его;
Выход. Для каждой
команды DEQUEUE выведите в отдельной строке номер удаляемого
студента.
|
Пример входа 1 |
Пример выхода 1 |
|
2 3 1 2 3 3 4 5 6 ENQUEUE 1 ENQUEUE 4 ENQUEUE 2 ENQUEUE 5 ENQUEUE 6 ENQUEUE 3 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE |
1 2 3 4 5 6 |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
2 3 1 2 3 3 4 5 6 ENQUEUE 1 ENQUEUE 4 ENQUEUE 2 DEQUEUE DEQUEUE ENQUEUE 5 ENQUEUE 3 ENQUEUE 6 DEQUEUE DEQUEUE DEQUEUE DEQUEUE |
1 2 4 5 6 3 |
|
Пример входа 3 |
Пример выхода 3 |
|
3 3 11 12 13 3 24 25 26 3 47 48 49 ENQUEUE 11 ENQUEUE 47 ENQUEUE 48 ENQUEUE 12 ENQUEUE 24 ENQUEUE 49 DEQUEUE DEQUEUE DEQUEUE ENQUEUE 13 DEQUEUE DEQUEUE DEQUEUE |
11 12 47 48 49 24 |
РЕШЕНИЕ
очередь
Анализ алгоритма
Для
каждого студента следует запомнить номер команды, которой он принадлежит. Пусть
teamBelongTo[ID] содержит номер
команды, которой принадлежит студент с идентификатором ID (ID ≤ 106).
int teamBelongTo[1000001];
Объявим
массив очередей teamQueue.
queue<int> teamQueue[1001];
В
каждую очередь входят только участники одной команды. Команд не более 1000.
Команды будем нумеровать с 0.
Студенты в очереди будут всегда стоять по группам
(командам). Объявим общую очередь combinedQueue,
которая содержит номера команд групп студентов, стоящих в очереди.
queue<int> combinedQueue;
Рассмотрим
выполнение команды ENQUEUE n. Определим команду team, которой принадлежит студент n. Если в очереди нет ни одного
студента из команды team, то студент номер n
становится в конец общей очереди. Представители команды team становятся
в конец общей очереди combinedQueue. Добавляем студента номер n в конец
очереди teamQueue[team].
Рассмотрим
выполнение команды DEQUEUE. В голове combinedQueue находится номер команды team студента, стоящего первым в очереди. Извлекаем студента из очереди.
Если это был последний студент из команды (teamQueue[team] становится пустой), то
удаляем голову очереди combinedQueue.
Пример
Рассмотрим
третий тест. Имеются три команды. Массив teamBelongTo имеет
вид:
-
команда 0 состоит из участников 11, 12, 13;
-
команда 1 состоит из участников 24, 25, 26;
-
команда 2 состоит из участников 47, 48, 49;
Промоделируем
первые 5 команд (все они имеют тип ENQUEUE). Общая очередь имеет вид (сверху возле каждого ID студента указан его номер команды):
Массив
очередей teamQueue имеет вид:
Общая
очередь combinedQueue
имеет вид:
Она
означает, что в общей очереди сначала стоит группа студентов из команды 0,
потом группа из команды 2 и в конце группа из команды 1.
Поступила
команда ENQUEUE
49. Вычисляем
какой команде принадлежит студент с ID = 49:
teamBelongTo[49] = 2. Следует проверить, есть ли представители команды
номер 2 в общей очереди. Для этого надо проверить, не пустая ли очередь teamQueue[2]. Нет, она не пустая, следовательно с
очередью combinedQueue делать ничего не нужно. Студент с ID = 49 будет занесен в конец очереди teamQueue[2], теперь станет teamQueue[2] = {47, 48, 49}.
Массив
очередей teamQueue имеет вид:
Далее
следуют три команды DEQUEUE.
При выполнениее первых двух команд из очереди удаляются студенты с номарами 11
и 12. Как только очередь teamQueue[0] станет пустой, номер команды 0 следует удалить из головы
очереди combinedQueue. Третьим из очереди уйдет студент
с ID = 47.
Состояние
очередей примет вид:
Массив
очередей teamQueue имеет вид:
Следующая
команда ENQUEUE
13. Студент с ID = 13 принадлежит команде номер teamBelongTo[13] = 0.
Представителей команды номер 0 в очереди нет (teamQueue[0] пустая). Следовательно номер команды 0
следует занести в конец очереди combinedQueue. Обновим teamQueue[0] = {13}.
Массив
очередей teamQueue имеет вид:
Реализация алгоритма
Для
каждого студента следует запомнить номер коанды, которой он принадлежит. Пусть teamBelongTo[ID] содержит номер
команды, которой принадлежит студент с идентификатором ID.
int teamBelongTo[1000001];
Объявим
массив очередей teamQueue. В каждую
очередь входят только участники одной команды. Команд не более 1000.
queue<int> teamQueue[1001];
Читаем количество команд numTeams.
Команды будем нумеровать с 0.
cin >> numTeams;
for (t = 0; t < numTeams; t++)
{
Чистим очередь команды номер t.
while (!teamQueue[t].empty()) teamQueue[t].pop();
Читаем данные команды номер t. В команде
номер t
находится numElem участников.
cin >> numElem;
while (numElem--)
{
cin >> elem;
Участник номер elem принадлежит
команде номер t.
teamBelongTo[elem] = t;
}
}
Объявим общую очередь combinedQueue, которая
содержит номера команд групп студентов, стоящих в очереди.
queue<int> combinedQueue;
Обрабатываем команды до конца файла.
while (cin >> command)
{
Пришел студент номер num. Вставка в очередь.
if (command[0] == 'E')
{
cin >> num;
Студент номер num принадлежит команде team.
team = teamBelongTo[num];
Если в очереди нет ни одного студента из команды team,
то студент номер num становится в конец общей очереди.
Представители команды team становятся в конец общей очереди combinedQueue.
if (teamQueue[team].empty())
combinedQueue.push(team);
Добавляем студента номер num в конец очереди teamQueue[team].
teamQueue[team].push(num);
}
else
{
В голове combinedQueue находится номер команды team студента, стоящего первым в очереди. Извлекаем студента из очереди.
Если это был последний студент из команды (teamQueue[team] становится пустой), то
удаляем голову очереди combinedQueue.
team = combinedQueue.front();
cout << teamQueue[team].front()
<< '\n';
teamQueue[team].pop();
if (teamQueue[team].empty())
combinedQueue.pop();
}
}