Решение: Контейнеры для пробирок
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов.
Компания планирует открыть лабораторию в одном из имеющихся пунктов. Перевозить биоматериалы разрешается на расстояние не более $M$. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 12 штук. Каждый транспортировочный контейнер используется для доставки пробирок только из одного пункта приёма, при этом из каждого пункта приёма может быть доставлено не более одного контейнера с неполной загрузкой. Пункт для лаборатории выбрали таким образом, чтобы количество доставляемых туда контейнеров с пробирками было максимальным. Определите необходимое количество контейнеров для доставки пробирок в эту лабораторию.
Даны два входных файла, файл А и файл B. Каждый файл в первой строке содержит два числа $N$ и $M$ ($1 \leq N \leq 10\,000\,000$, $1 \leq M \leq 10\,000\,000$). В каждой из следующих $N$ строк находятся два числа: номер пункта и количество пробирок, принимаемых на этом пункте за сутки. Все числа натуральные, количество пробирок в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения вдоль автомагистрали, считая от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B. Для выполнения задания используйте данные из прилагаемых файлов.
Решение по шагам
4 шагаЕсли лаборатория открыта в пункте с координатой $x$, доставлять пробирки можно из пунктов с координатами от $x-M$ до $x+M$.
Для каждого пункта с количеством пробирок $q_i$ вычисляем число контейнеров: один неполный контейнер допускается, поэтому используется значение $\left\lceil\dfrac{q_i}{12}\right\rceil$.
Поскольку пункты отсортированы по координате, множество подходящих пунктов образует непрерывное окно. Его можно искать методом двух указателей за $O(N)$ после чтения файла.
Для каждого возможного положения лаборатории суммируем число контейнеров в соответствующем окне и сохраняем максимальную сумму. Ту же процедуру выполняем отдельно для файлов А и B.
Определяется по данным файлов А и B; вложения с исходными данными недоступны.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать контейнеры как $q_i / 12$ без округления вверх.
Разрешить перевозку из пунктов на расстоянии более $M$.
Рассматривать только пункты слева или только пункты справа от лаборатории.
Использовать полный перебор всех пар границ окна для файла B.