Решение: Минимальная доставка по кольцу
Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна $N$ километров. Нулевой и $N$-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна.
Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Дано два входных файла — файл A и файл B. Каждый файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$) — количество пунктов питания на кольцевой трассе. В следующих $N$ строках находятся количества комплектов питания в пунктах. Все числа натуральные, количество комплектов в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения на трассе, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем для файла B. Для файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных положений цеха.
Решение по шагам
5 шаговПусть пункты пронумерованы от $0$ до $N-1$, а в пункте $i$ находится $a_i$ комплектов. Если цех расположен в пункте $k$, расстояние до пункта $i$ равно $\min(|i-k|, N-|i-k|)$.
Стоимость положения $k$ равна $F(k)=\sum_{i=0}^{N-1} a_i\min(|i-k|,N-|i-k|)$. Прямой перебор всех пар имеет сложность $O(N^2)$ и не подходит для файла B.
Разделите кольцо относительно пункта $k$ на дуги, расстояния на которых равны последовательным значениям $1,2,\ldots,\lfloor N/2\rfloor$. С помощью префиксных сумм $\sum a_i$ и $\sum i a_i$ стоимость каждой дуги вычисляется за $O(1)$.
Последовательно рассмотрите все $N$ возможных положений цеха, вычисляя стоимость каждого положения по формулам для соответствующих циклических диапазонов. Минимальная из полученных стоимостей является ответом для одного файла.
Тот же алгоритм примените отдельно к файлам A и B. Его сложность составляет $O(N)$ по времени и $O(N)$ по памяти либо $O(1)$ дополнительной памяти при потоковой реализации с хранением необходимых сумм.
Численные значения для файлов A и B определяются по приложенным входным файлам; сами файлы в условии не предоставлены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Использовать обычное расстояние по прямой вместо кратчайшего расстояния по кольцу.
Перебирать все пары «положение цеха — пункт питания», получая сложность $O(N^2)$.
Забыть учесть циклический переход от пункта $N-1$ к пункту $0$.
Переполнить 32-битный целочисленный тип при вычислении суммарной стоимости.