Решение: Минимальная стоимость доставки
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 40 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Дано два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($1 \leq N \leq 10\,000\,000$). В каждой из следующих $N$ строк находятся два числа: номер пункта и количество пробирок в этом пункте. Все числа натуральные, количество пробирок в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение по шагам
4 шагаДля каждого пункта заменяем количество пробирок числом контейнеров, округляя вверх до целого:
$$w_i = \left\lceil \dfrac{q_i}{40} \right\rceil$$Если лаборатория расположена в пункте с координатой $x$, стоимость доставки равна:
$$S(x)=\sum_{i=1}^{N} w_i\lvert x_i-x\rvert$$Функция $S(x)$ минимальна в точке взвешенной медианы. Так как пункты уже отсортированы по координате, достаточно найти первый пункт, для которого сумма контейнеров слева с учётом текущего пункта достигает не менее половины общего числа контейнеров.
После выбора пункта-медианы стоимость можно вычислить одним проходом по данным. Для файла B вместо перебора всех пунктов используется линейный алгоритм с асимптотической сложностью $O(N)$.
Числовые значения для файлов A и B определяются по приложенным входным файлам.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Использовать количество пробирок вместо количества контейнеров.
Округлять общее количество пробирок, а не количество контейнеров в каждом отдельном пункте.
Перебирать все варианты расположения лаборатории для файла B.
Выбирать обычную медиану координат без учёта числа контейнеров.