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