Минимальная стоимость перевозки
У медицинской компании есть $N$ пунктов приёма биоматериалов, расположенных вдоль автомагистрали. Для каждого пункта известны его номер и количество ежедневно принимаемых пробирок. Пробирки перевозят в контейнерах вместимостью не более 36 штук. Каждый контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Лабораторию располагают в одном из пунктов приёма так, чтобы общая стоимость доставки была минимальной. Стоимость перевозки из пункта равна произведению расстояния до лаборатории на количество контейнеров с пробирками. Необходимо определить минимальную общую стоимость доставки для файлов A и B.
Каждый входной файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$). В следующих $N$ строках записаны номер пункта и количество пробирок в нём. Пункты перечислены в порядке их расположения вдоль дороги. Для файла A допускается переборный алгоритм, а для файла B необходимо использовать более эффективный алгоритм. Типовой пример имеет иллюстративный характер; для получения ответа нужны данные из прилагаемых файлов.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждого пункта сначала вычислите число контейнеров: $\left\lceil q_i/36 \right\rceil$.
2Наводящая — какие числа считатьуровень 2 из 3
Стоимость для выбранного пункта — сумма произведений $|x_i-x_j|c_i$, где $c_i$ — число контейнеров в пункте $i$.
3Прямая — фактически решениеуровень 3 из 3
Для файла B используйте переход между соседними пунктами через префиксную сумму контейнеров слева и общую сумму контейнеров: изменение стоимости вычисляется за $O(1)$.