Решение: Обработка журнала сервера
Сервер выполняет запросы на передачу данных. Для каждого запроса в журнале указаны время регистрации, идентификатор клиента и объём переданных данных. Переданные данные сохраняются в специальном разделе памяти сервера вместимостью $K$ Кбайт. Каждый раз, когда для очередного запроса недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных данных, после чего освобождает раздел и продолжает выполнение запросов. Определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов двух наибольших резервных копий, созданных не позднее 11:59:59.
В первой строке входного файла находятся натуральные числа $N$ и $K$: количество записей журнала и вместимость раздела памяти в Кбайт. В каждой из следующих $N$ строк записаны время в формате ЧЧ:ММ:СС, идентификатор клиента $C$ и объём данных $S$ в Кбайт. Выведите два числа: сначала идентификатор клиента, затем сумму объёмов двух наибольших подходящих резервных копий.
Решение по шагам
5 шаговДля каждого идентификатора клиента поддерживаем суммарный объём переданных данных. Это можно сделать словарём, не храня весь журнал.
$$total[C] \mathrel{+}= S$$Поддерживаем объём данных, накопленных в специальном разделе. Если очередной запрос не помещается, текущий объём становится резервной копией, после чего раздел освобождается.
$$current + S > K \Rightarrow backups.append(current),\ current = 0$$После освобождения раздела добавляем объём текущего запроса. Так моделируется последовательная обработка журнала.
$$current \mathrel{+}= S$$Из словаря выбираем идентификатор с наибольшей суммой. Среди резервных копий, созданных не позднее 11:59:59, выбираем две наибольшие и складываем их объёмы.
Времена можно сравнивать как строки формата ЧЧ:ММ:СС или перевести в секунды. Так как записи идут в хронологическом порядке, момент создания копии определяется временем запроса, перед которым раздел пришлось освободить.
Идентификатор клиента с максимальным суммарным объёмом и сумма двух наибольших резервных копий до 11:59:59; численные значения определяются данными прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Создают резервную копию после добавления запроса, хотя копирование выполняется перед добавлением, если запрос не помещается.
Забывают обнулить объём раздела после создания резервной копии.
Учитывают резервные копии после 11:59:59.
Ищут двух клиентов с наибольшими объёмами вместо двух наибольших резервных копий.
Хранят все записи журнала и используют слишком много памяти при ограничении $N < 1\,000\,000$.