Arithmétique Difficile#12257

Arithmétique Difficile (Corrigé)

Auteur du Problème:	Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Le tableau cible doit être une PA : $b_{i} = m \cdot i + c$ b_i=m\cdot i+c. Nous ne pouvons qu'augmenter les entrées, donc pour une pente fixe $m$ , le décalage réalisable le plus petit est

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

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

Alors le coût total (somme des augmentations) est

co u ˆ t (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{coût}(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

Posons $S = \frac{n ( n + 1 )}{2}$ S=\frac{n(n+1)}{2} et $A = \sum_{i} a_{i}$ A=\sum_i a_i. Définissons

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)

Alors $co u ˆ t (m) = F (m) - A$ \text{coût}(m)=F(m)-A. C'est le maximum ponctuel des lignes en $m \Rightarrow$ une fonction convexe, unimodale sur les entiers. Par conséquent, nous pouvons trouver son minimum avec la recherche convexe discrète standard (comparer $F (M)$ ) contre $f (M + 1)$ f(M+1)).

Précalculer $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 Alors

F (m) = i max (ba_{i} + m \cdot w_{i}), r e ˊ ponse = m min F (m) - A

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

Complexité $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