Решение: Камера хранения
Задание выполняется с использованием прилагаемых файлов. Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения. Во второй строке находится натуральное число N, не превышающее 1000, — количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки.
Решение по шагам
5 шаговСоздаём массив времени освобождения ячеек. Изначально все ячейки свободны; это можно обозначить временем освобождения 0.
Заявки обрабатываются в порядке, указанном во входном файле. Для заявки с временем сдачи багажа t просматриваем ячейки по возрастанию номеров.
Ячейка свободна для новой заявки, если её время освобождения строго меньше t. Это учитывает условие, что воспользоваться только что освобождённой ячейкой можно начиная со следующей минуты.
Если подходящая ячейка найдена, размещаем в ней багаж, записываем её новое время освобождения, увеличиваем количество обслуженных пассажиров и обновляем минимальный номер среди ячеек, занятых последними.
Численные значения результата должны быть получены из прилагаемого входного файла. В предоставленных данных содержимое входного файла отсутствует, поэтому вычислить конкретную пару чисел невозможно.
Определяется по прилагаемому входному файлу; его содержимое не предоставлено.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Разрешают занять ячейку в ту же минуту, в которую она освобождается.
Выбирают любую свободную ячейку вместо ячейки с минимальным номером.
Сортируют заявки по времени, хотя условие требует обрабатывать их в порядке входного файла.
При определении последней занятой ячейки выбирают максимальный номер вместо минимального при совпадении времени.