Решение: Минимальная стоимость доставки
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 46 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Входные данные: два файла, файл A и файл B. Каждый файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$). В каждой из следующих $N$ строк находятся два натуральных числа: номер пункта и количество пробирок в этом пункте. Количество пробирок в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Типовой пример организации данных во входном файле:
$6$
$1\ 100$
$2\ 200$
$5\ 4$
$7\ 3$
$8\ 2$
$10\ 190$
При типовых исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит $1 \cdot 2 + 3 \cdot 1 + 5 \cdot 1 + 6 \cdot 1 + 8 \cdot 2$. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение по шагам
4 шагаДля пункта с количеством пробирок $q_i$ число контейнеров равно округлению вверх:
$$c_i=\left\lceil\frac{q_i}{46}\right\rceil$$Если лаборатория находится в пункте с координатой $x_k$, стоимость определяется суммой расстояний до всех пунктов с весами $c_i$:
$$S_k=\sum_{i=1}^{N} c_i\lvert x_i-x_k\rvert$$Для первой позиции стоимость вычисляется напрямую. При переходе от пункта $k$ к пункту $k+1$ стоимость изменяется на расстояние между этими пунктами, умноженное на разность суммарного числа контейнеров справа и слева:
$$S_{k+1}=S_k+(x_{k+1}-x_k)(C_{\text{left}}-C_{\text{right}})$$Последовательно вычисляются все значения $S_k$, после чего выбирается минимальное. Такой алгоритм работает за $O(N)$ и подходит для файла B.
Численные ответы определить невозможно без содержимого файлов A и B.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Округляют общее количество пробирок, а не количество пробирок в каждом отдельном пункте.
Используют расстояние между соседними номерами вместо разности координат пунктов.
Пересчитывают стоимость для каждой лаборатории с нуля, получая алгоритм сложности $O(N^2)$.
Забывают, что лаборатория может быть открыта только в одном из пунктов приёма.