Карточки
Тесты
Главная
Курсы
Подписка
26. Прикладная задача: #298080
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение $1$ мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение $24$ ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
Это прямое моделирование. Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени сдачи багажа — обслуживать пассажиров надо в порядке прихода.
Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $t$ может занять ячейку, если это число меньше $t$ — так реализуется правило «начиная со следующей минуты после освобождения». Перебираем ячейки по возрастанию номера и берём первую подходящую, чем и обеспечивается требование про минимальный номер. Если подходящей нет, пассажир уходит.
Попутно считаем принятых и запоминаем, кто занял ячейку последним по времени; при совпадении времени берём меньший номер ячейки.
f = open('26-22.txt')
K = int(f.readline())
N = int(f.readline())
req = [tuple(map(int, f.readline().split())) for _ in range(N)]
req.sort() # по времени сдачи багажа
free = [0] * K # время, когда ячейка освободится
cnt = 0
last_t, last_cell = -1, None
for t, e in req:
for i in range(K):
if free[i] < t: # доступна со следующей минуты
free[i] = e
cnt += 1
if t > last_t:
last_t, last_cell = t, i + 1
elif t == last_t and i + 1 < last_cell:
last_cell = i + 1
break
print(cnt, last_cell) # 344 53
Проверка. Ячеек $210$, заявок $987$, успешными оказались $344$ пассажира. Последняя сдача среди них произошла на $999$-й минуте, и такой пассажир был один — он занял ячейку $53$. На типовом примере из условия программа выдаёт $4$ и $1$.
20
