Çətin Aritmetik#12257

Çətin Aritmetik (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Hədəf massiv AP olmalıdır: $b_{i} = m \cdot i + c$ b_i=m\cdot i+c. Biz yalnız girişləri artıra bilərik, buna görə sabit meyl $m$ üçün ən kiçik mümkün dəyişiklik

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

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

Sonra ümumi xərc (artımların cəmi)

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} və $A = \sum_{i} a_{i}$ A=\sum_i a_i təyin edin.

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)

Sonra $cost (m) = F (m) - A$ \text{cost}(m)=F(m)-A. Bu, $m$ üzrə xətlərin nöqtəvi maksimumudur $\Rightarrow$ tam ədədlərdə konveks, unimodal funksiya. Buna görə də, onun minimumunu standart diskret konveks axtarışla tapa bilərik (müqayisə $F (M)$ ) vs $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 əvvəlcədən hesablayın. Sonra

F (m) = i max (ba_{i} + m \cdot w_{i}), cavab = m min F (m) - A

F(m)=\max_i(\texttt{ba}_i+m\cdot \texttt{w}_i),\qquad \text{cavab}=\min_m F(m)-A

Mürəkkəblik $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