Минимальная доставка по кольцу
Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна $N$ километров. Нулевой и $N$-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна.
Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Дано два входных файла — файл A и файл B. Каждый файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$) — количество пунктов питания на кольцевой трассе. В следующих $N$ строках находятся количества комплектов питания в пунктах. Все числа натуральные, количество комплектов в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения на трассе, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем для файла B. Для файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных положений цеха.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Для каждого положения цеха стоимость равна сумме произведений количества комплектов на кратчайшее расстояние по кольцу.
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Разбейте пункты относительно выбранного положения на левую и правую части. Для быстрого вычисления сумм используйте префиксные суммы количеств комплектов и их позиций.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Для каждого пункта $k$ вычисляйте расстояния до пунктов на дугах длиной не более $\lfloor N/2 \rfloor$. Стоимость всех положений можно получить за $O(N)$ после построения префиксных сумм; выберите минимальное значение.