[Python] Cumulative sum ABC186D

ABC186D

Sort the inputA_1\leq\ldots\leq A_NIt is good as. At this timei<jAgainst|A_i-A_j| = A_j-A_iAnd you can simplify the calculation.

eachiabout\sum_{j=i+1}^{N}|A_i-A_j|=(\sum_{j=i+1}^{N}A_j)-(N-i)A_iAnd this is in advanceABy calculating the cumulative sum ofO(1)You can find it at. ThereforeO(N\log N)So I solved this problem.

If you're not sure, AtCoder ABC 186 D --Sum of difference (brown, 400 points)

`Sample code`


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)

Recommended Posts

[Python] Cumulative sum ABC186D

[Python] Cumulative sum ABC179D

Learn cumulative sum in Python

[Python] ABC175D

[Python] DP ABC184D

[Python] UnionFind ABC177D

[Python] Interval scheduling ABC103D

[Python] Binary search ABC155D

Solve ABC159-D in Python

Implement sum in Python

[Python] Dynamic programming ABC015D