Решение: Минимальная стоимость вывоза мусора
На каждом 3-м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна $3N$ километров. Нулевой километр и $3N$-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов расположен в одном из пунктов сбора мусора таким образом, что общая стоимость доставки мусора из всех пунктов минимальна.
Определите минимальную суммарную стоимость доставки мусора из всех пунктов сбора в центр переработки отходов.
Даны два входных файла: файл A и файл B. Каждый файл в первой строке содержит число $N$ ($1 \leqslant N \leqslant 10\,000\,000$) — количество пунктов сбора мусора. В следующих $N$ строках записано количество мусора в контейнере. Все числа натуральные, количество мусора в каждом пункте не превышает 1000. Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
Для обработки файла B необходимо использовать алгоритм, не перебирающий все возможные положения центра переработки.
Решение по шагам
5 шаговПронумеруем пункты от $0$ до $N-1$, а количество мусора в пункте $i$ обозначим через $a_i$. Расстояние между пунктами $i$ и $j$ равно $3\cdot\min(|i-j|,N-|i-j|)$.
Для центра в пункте $0$ вычислим начальную стоимость $C_0$, просуммировав для каждого пункта произведение количества мусора на кратчайшее расстояние до пункта $0$.
Пусть $S=\sum a_i$. При переносе центра из пункта $i$ в пункт $i+1$ для мусора, находящегося на одной стороне разреза кольца, расстояние увеличивается на 3 км, а для мусора на другой стороне уменьшается на 3 км. Поэтому стоимость можно пересчитывать за $O(1)$.
Для каждого следующего центра поддерживаем сумму мусора, оказавшегося пройденной частью кольца. Пересчитываем стоимость, сравниваем её с текущим минимумом и сохраняем наименьшее значение.
Алгоритм выполняется за $O(N)$ времени и $O(N)$ памяти при хранении всех значений либо за $O(N)$ времени и $O(1)$ дополнительной памяти при последовательной обработке после вычисления начальной стоимости.
Численные значения для файлов A и B нельзя определить без содержимого приложенных входных файлов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Использование обычного расстояния по прямой вместо кратчайшего расстояния по кольцу.
Забывание множителя 3, так как соседние пункты находятся через 3 км.
Перебор всех пар «центр — пункт» для файла B.
Использование 32-битного целого типа для сумм и стоимости.