Складна арифметика#12257

Складна арифметика (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Розв'язок

Цільовий масив повинен бути арифметичною прогресією: $b_{i} = m \cdot i + c$ b_i=m\cdot i+c. Ми можемо лише збільшувати значення, тому для фіксованого нахилу $m$ найменше можливе зсув це

c = i max (a_{i} - m \cdot i)

c=\max_i\,(a_i-m\cdot i)

Тоді загальна вартість (сума приростів) дорівнює

cost (m) = i = 1 \sum n (m \cdot i + c - a_{i}) = m \cdot (i = 1 \sum n i) + n \cdot i max (a_{i} - mi) - i = 1 \sum n a_{i}

\text{cost}(m)=\sum_{i=1}^n (m\cdot i+c-a_i)=m\cdot\Big(\sum_{i=1}^n i\Big)+n\cdot\max_i(a_i-m i)-\sum_{i=1}^n a_i

Нехай $S = \frac{n ( n + 1 )}{2}$ S=\frac{n(n+1)}{2} та $A = \sum_{i} a_{i}$ A=\sum_i a_i. Визначимо

F (m) = i max (n a_{i} + m \cdot (S - n i))

F(m)=\max_i\big(n\,a_i+m\cdot(S-n\,i)\big)

Тоді $cost (m) = F (m) - A$ \text{cost}(m)=F(m)-A. Це точковий максимум прямих у $m \Rightarrow$ опукла, унімо́дальна функція на цілих числах. Отже, ми можемо знайти її мінімум за допомогою стандартного дискретного опуклого пошуку (порівняти $F (M)$ ) з $f (M + 1)$ f(M+1)).

Попередньо обчисліть $ba_{i} = n \cdot a_{i}$ \texttt{ba}_i=n\cdot a_i, $w_{i} = S - n \cdot i$ \texttt{w}_i=S-n\cdot i. Тоді

F (m) = i max (ba_{i} + m \cdot w_{i}), відповідь = m min F (m) - A

F(m)=\max_i(\texttt{ba}_i+m\cdot \texttt{w}_i),\qquad \text{відповідь}=\min_m F(m)-A

Складність $O (n lo g)$ \mathcal{O}(n\log)

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    S=n*(n+1)//2
    ba=[n*x for x in a]
    w=[S-n*(i+1) for i in range(n)]
    A=sum(a)
    def F(m):
        z=-10**30
        for i in range(n):
            v=ba[i]+m*w[i]
            if v>z:z=v
        return z
    L=-10**9
    R=10**9
    while L<R:
        M=(L+R)//2
        if F(M)<=F(M+1):R=M
        else:L=M+1
    assert(F(L)<=9*10**18)
    print(F(L)-A)

Python