Задание №27 — Оптимальный алгоритм для большого количества данных

Решение:

Занумеруем пункты числами $0,1,\dots,N-1$ (пункт $c$ — это $(c+1)$-й километр), вес пункта $w_c$ — количество комплектов питания. Трасса кольцевая и движение двустороннее, поэтому расстояние от цеха в пункте $c$ до пункта $p$ равно $\min(d,\,N-d)$, где $d=(p-c)\bmod N$. Нужно найти $\min_c C(c)$, где $C(c)=\sum_p w_p\min(d,N-d)$.

Прямой перебор всех $c$ с пересчётом суммы — это $O(N^2)$, для файла B это нереально. Заметим, что при фиксированном $c$ пункты разбиваются на две дуги: до $A=\lfloor N/2\rfloor$ шагов вперёд (там расстояние равно смещению $d$) и до $B=\lfloor (N-1)/2\rfloor$ шагов назад (расстояние равно смещению $e$). Так как $A+B+1=N$, каждый пункт учитывается ровно один раз, и $$C(c)=\sum_{d=0}^{A} d\,w_{c+d}+\sum_{e=1}^{B} e\,w_{c-e}$$ (индексы по модулю $N$).

Обе суммы берутся по окну постоянной длины, которое сдвигается вместе с $c$. Продублируем массив весов ($ww=w+w$) и построим две префиксные суммы: $P_1[t]=\sum_{i\lt t} ww_i$ и $P_2[t]=\sum_{i\lt t} i\,ww_i$. Тогда, подставляя $t=c+d$ и $t=c+N-e$, получаем $$\sum_{d=0}^{A} d\,w_{c+d}=\bigl(P_2[c+A+1]-P_2[c]\bigr)-c\bigl(P_1[c+A+1]-P_1[c]\bigr),$$ $$\sum_{e=1}^{B} e\,w_{c-e}=(c+N)\bigl(P_1[c+N]-P_1[c+N-B]\bigr)-\bigl(P_2[c+N]-P_2[c+N-B]\bigr).$$ Каждое значение $C(c)$ считается за $O(1)$, весь алгоритм — за $O(N)$.

def solve(name):
    f = open(name)
    n = int(f.readline())
    w = [int(f.readline()) for _ in range(n)]   # w[c] — пункт (c+1)-го километра
    a = n // 2            # смещения «вперёд»: 0, 1, ..., a
    b = (n - 1) // 2      # смещения «назад»:  1, 2, ..., b   (a + b + 1 = n)
    ww = w + w            # удваиваем массив, чтобы не считать индексы по модулю
    p1 = [0] * (2 * n + 1)          # p1[t] = сумма ww[0..t-1]
    p2 = [0] * (2 * n + 1)          # p2[t] = сумма i*ww[i] для i = 0..t-1
    for t in range(2 * n):
        p1[t + 1] = p1[t] + ww[t]
        p2[t + 1] = p2[t] + t * ww[t]
    best = None
    for c in range(n):
        hi = c + a + 1
        fwd = (p2[hi] - p2[c]) - c * (p1[hi] - p1[c])
        lo = c + n - b
        bwd = (c + n) * (p1[c + n] - p1[lo]) - (p2[c + n] - p2[lo])
        cost = fwd + bwd
        if best is None or cost < best:
            best = cost
    return best

print(solve('A.txt'), solve('B.txt'))

Проверка на примере из условия ($N=6$, веса $8,20,5,13,7,19$): минимум достигается в пункте 6 и равен $1\cdot 7+0\cdot 19+1\cdot 8+2\cdot 20+3\cdot 5+2\cdot 13=96$.Для файла A минимум равен $141\,530$ (цех в пункте $105$), для файла B — $18\,192\,010\,182\,272$.Ответ: 141530 18192010182272