Решение: Минимальная стоимость перевозки
У медицинской компании есть $N$ пунктов приёма биоматериалов, расположенных вдоль автомагистрали. Для каждого пункта известны его номер и количество ежедневно принимаемых пробирок. Пробирки перевозят в контейнерах вместимостью не более 36 штук. Каждый контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Лабораторию располагают в одном из пунктов приёма так, чтобы общая стоимость доставки была минимальной. Стоимость перевозки из пункта равна произведению расстояния до лаборатории на количество контейнеров с пробирками. Необходимо определить минимальную общую стоимость доставки для файлов A и B.
Каждый входной файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$). В следующих $N$ строках записаны номер пункта и количество пробирок в нём. Пункты перечислены в порядке их расположения вдоль дороги. Для файла A допускается переборный алгоритм, а для файла B необходимо использовать более эффективный алгоритм. Типовой пример имеет иллюстративный характер; для получения ответа нужны данные из прилагаемых файлов.
Решение по шагам
4 шагаДля каждого пункта заменяем количество пробирок на число контейнеров:
$$c_i=\left\lceil\frac{q_i}{36}\right\rceil$$Стоимость лаборатории в пункте с координатой $x_j$ равна:
$$S_j=\sum_{i=1}^{N}|x_i-x_j|c_i$$Для эффективного вычисления отсортированных пунктов поддерживаем сумму контейнеров слева. При переходе от пункта $j$ к следующему пункту $j+1$ на расстояние $d=x_{j+1}-x_j$ стоимость изменяется на:
$$S_{j+1}=S_j+d\left(2P_j-C\right)$$Здесь $P_j$ — суммарное количество контейнеров в пунктах от 1 до $j$, а $C$ — общее количество контейнеров. Минимальное значение среди всех $S_j$ является ответом.
Числовой ответ невозможно определить: файлы A и B не приложены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Использовать количество пробирок вместо количества контейнеров.
Округлять общее число пробирок, а не число пробирок в каждом отдельном пункте.
Для файла B вычислять стоимость заново для каждого пункта.
Не учитывать, что лаборатория может быть открыта только в одном из пунктов приёма.