题意解析
本题要求我们求
∑i=1N−1∑j=i+1N∣Ai−Aj∣\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \vert A_i - A_j \vert i=1∑N−1 j=i+1∑N ∣Ai −Aj ∣
带着这个绝对值是不好做,我们考虑把绝对值符号去掉。
上面这个式子本意就是求数组中元素两两之间的差的绝对值,数组的顺序是不影响答案的,所以我们可以把整个数组排序得到数组 A′A'A′:
A1′,A2′,A3′,⋯ ,AN′(A1′≤A2′≤A3′≤⋯≤AN′)A_1', A_2', A_3', \cdots, A_N'(A_1' \le A_2' \le A_3' \le \cdots \le A_N')A1′ ,A2′ ,A3′ ,⋯,AN′ (A1′ ≤A2′ ≤A3′ ≤⋯≤AN′ )。
那么,我们可以将上式转化为:
∑i=1N−1∑j=i+1NAj′−Ai′\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_j' - A_i' i=1∑N−1 j=i+1∑N Aj′ −Ai′
这样就可以把这个绝对值符号去掉,从而我们可以继续转化这个式子:
((A2′−A1′)+(A3′−A1′)+⋯+(AN′−A1′))+((A3′−A2′)+(A4′−A2′)+⋯+(AN′−A2′))+⋮((AN−1′−AN−2′)+(AN′−AN−2)′)+((AN′−AN−1′))((A_2' - A_1') + (A_3' - A_1') + \cdots + (A_N' - A_1')) + \\ ((A_3' - A_2') + (A_4' - A_2') + \cdots + (A_N' - A_2')) + \\ \vdots \\ ((A_{N - 1}' - A_{N-2}') + (A_{N}' - A_{N-2})') + \\
((A_N' - A_{N-1}')) ((A2′ −A1′ )+(A3′ −A1′ )+⋯+(AN′ −A1′ ))+((A3′ −A2′ )+(A4′ −A2′ )+⋯+(AN′ −A2′ ))+⋮((AN−1′ −AN−2′ )+(AN′ −AN−2 )′)+((AN′ −AN−1′ ))
化简得到:
(A2′+A3′+⋯+AN′−A1′×(N−1))+(A3′+A4′+⋯+AN′−A2′×(N−2))+(AN−1′+AN′−AN−2′×2)+(AN′−AN−1′)(A_2' + A_3' + \cdots + A_N' - A_1' \times (N - 1)) + \\ (A_3' + A_4' + \cdots + A_N' - A_2' \times (N - 2)) + \\ (A_{N-1}' + A_{N}' - A_{N-2}' \times 2) + \\ (A_N' - A_{N-1}') (A2′ +A3′ +⋯+AN′ −A1′ ×(N−1))+(A3′ +A4′
+⋯+AN′ −A2′ ×(N−2))+(AN−1′ +AN′ −AN−2′ ×2)+(AN′ −AN−1′ )
从上面这个结果我们可以发现,这个式子最终的答案就是算每个 AiA_iAi 在答案中产生的贡献,有加有减。
每个 Ai′A_i'Ai′ 会减掉 N−iN - iN−i 次,会加上 i−1i - 1i−1 次,那么我们就可以得到最终的式子:
∑i=1N−1∑j=i+1N∣Ai−Aj∣=∑i=1N−1∑j=i+1NAj′−Ai′=∑i=1N(i×2−N+1)×Ai′\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \vert A_i - A_j \vert = \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_j' - A_i' = \sum_{i=1}^{N} (i \times 2 - N + 1) \times A_i' i=1∑N−1 j=i+1∑N ∣Ai −Aj ∣=i=1∑N−1 j=i+1∑N Aj′ −Ai′ =i=1∑N (i×2−N+1)×Ai′
上面这个式子,我们只需要将排序后的 A′A'A′ 进行一次遍历计算即可。
AC 代码
复杂度分析
将数组 AAA 排序的时间复杂度为 O(NlogN)\mathrm{O}(N\log{N})O(NlogN),遍历 A′A'A′ 计算答案的时间复杂度为 O(N)\mathrm{O}(N)O(N),总的时间复杂度为: O(NlogN)\mathrm{O}(N\log{N})O(NlogN)。