[Python] 累積和 ABC186D

#ABC186D

入力をソートして $A_1\leq\ldots\leq A_N$ として良いです。このとき $i<j$に対して $|A_i-A_j| = A_j-A_i$ となり、計算を単純化することができます。

各 $i$ について $\sum_{j=i+1}^{N}|A_i-A_j|=(\sum_{j=i+1}^{N}A_j)-(N-i)A_i$ となり、これは予め $A$ の累積和を計算しておくことでそれぞれ $O(1)$ で求めることができます。よって $O(N\log N)$ でこの問題が解けました。

よくわからない場合は、
AtCoder ABC 186 D - Sum of difference (茶色, 400 点)

サンプルコード

n = int(input())
a = list(map(int,input().split()))
a.sort()
suma= sum(a)
ans = 0
for i in range(n-1):
    # print()
    suma -= a[i]
    ans += suma - a[i]*(n-i-1) 
 
print(ans)