14. Фоновая обработка заданий — повышенный уровень
Очередь и словарь вместе
Что хранит. Очередь хранит порядок идентификаторов, а словарь связывает каждый идентификатор с его текущими данными. Эти коллекции отвечают на разные вопросы об одних записях.
Для чего используют. Подходит, когда задания обрабатываются по очереди, но их состояние нужно читать или менять по идентификатору.
Основные операции
| Запись на C# | Назначение |
|---|
order.Enqueue(id) | Добавить идентификатор в конец очереди. |
order.Peek() / order.Dequeue() | Посмотреть или извлечь первый идентификатор; очередь должна быть непустой. |
order.Count | Число записей в очереди; оно может включать отменённые записи. |
state[id] = value | Создать или обновить состояние по ключу. |
state.TryGetValue(id, out value) | Безопасно прочитать состояние. |
state.ContainsKey(id) | Проверить, известен ли идентификатор. |
Пример
Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.
Queue<int> order = new Queue<int>();
Dictionary<int, int> remaining = new Dictionary<int, int>();
order.Enqueue(42);
remaining[42] = 3;
int id = order.Dequeue(); // Очередь выбирает задание.
remaining[id]--; // Словарь хранит его данные.
order.Enqueue(id);
Console.WriteLine(remaining[order.Peek()]);
Вывод:
2
Важно. Изменение словаря само по себе не удаляет элемент очереди. При отмене можно пометить состояние, а ненужную запись пропустить при извлечении.
Для этой задачи
- Один шаг. Извлеките первое задание, уменьшите остаток работы и при необходимости верните идентификатор в конец.
Фоновый обработчик делит время между заданиями. Изначально задания стоят в очереди в порядке ввода. За один шаг обработчик извлекает первое задание и уменьшает его оставшийся объём работы на 1. Если объём стал нулевым, задание завершено; иначе оно возвращается в конец очереди. Выполните не более k шагов. Если очередь опустела, работа сразу заканчивается.
Входные данные
Первая строка содержит n и k. Далее идут n строк id work: уникальный идентификатор задания и его начальный объём работы.
Выходные данные
В первой строке выведите идентификаторы завершённых заданий в порядке завершения через пробел или EMPTY. Во второй строке выведите r — число оставшихся заданий. Далее выведите r строк id remaining в порядке текущей очереди, начиная с первого. При r = 0 дополнительных строк нет.
Не выводите приглашения к вводу и пояснения. Служебные слова в ответах пишите в указанном регистре.
Ограничения
0 ≤ n ≤ 100000; 0 ≤ k ≤ 200000; 1 ≤ id, work ≤ 10⁹. Идентификаторы во входных данных различны.
| № | Входные данные | Выходные данные |
|
1
|
3 4
10 2
20 1
30 3
|
20 10
1
30 2
|
|
2
|
2 10
5 1
8 2
|
5 8
0
|
Напишите программу
Auto