26. Прикладная задача: Ответ для приведённого примера: 101 252000
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор клиентского устройства, с которого на сервер был передан наибольший суммарный объём данных не позднее $11{:}59{:}59$, а также сумму объёмов двух наибольших резервных копий специального раздела (в Кбайт).
Задача распадается на две независимые части, которые считаются за один проход по журналу.
Первая — моделирование раздела памяти. Держим счётчик накопленного объёма. Для очередного запроса проверяем, влезает ли он: если накопленное плюс новый объём превышает вместимость $K$, сервер сначала делает резервную копию того, что уже лежит в разделе, и обнуляет счётчик, и только потом кладёт туда новый запрос. Обратите внимание на порядок: в копию попадает объём до добавления текущего запроса. В примере это хорошо видно — в $05{:}05{:}05$ копируются $130000$ Кбайт, накопленные первыми двумя запросами, а сам запрос на $90000$ уже начинает новый цикл.
Вторая — суммы по клиентам. Складываем объёмы по идентификаторам, но только для запросов не позднее $11{:}59{:}59$. Время удобно сравнивать прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически, поэтому разбирать его на числа не нужно.
from collections import defaultdict
f = open('26-20.txt')
n, K = map(int, f.readline().split())
total = defaultdict(int)
backups = []
cur = 0
for _ in range(n):
t, c, s = f.readline().split()
s = int(s)
if cur + s > K: # свободной памяти не хватает
backups.append(cur) # резервная копия накопленного
cur = 0
cur += s
if t <= '11:59:59': # строки в формате ЧЧ:ММ:СС сравниваются как время
total[int(c)] += s
backups.sort(reverse=True)
best = max(total, key=lambda c: total[c])
print(best, backups[0] + backups[1]) # 9517 46436
Проверка. В журнале $15005$ записей, вместимость раздела $23218$ Кбайт, резервных копий получилось $1116$. Две наибольшие оказались по $23218$ Кбайт каждая, то есть ровно под завязку, в сумме $46436$. По клиентам до полудня лидирует устройство $9517$ с объёмом $134167$ Кбайт, следующее за ним — $6877$ со $121879$. На типовом примере из условия программа выдаёт $101$ и $252000$.