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