算法
(主客転倒) $O(n)$
注意到本题可以任取两数,所以可以先对原序列排序。
于是
$$ \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n |A_i - A_j| = \sum_{j = 1}^n \Big((j - 1)A_j - \sum_{i = 1}^{j - 1} A_i\Big) $$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
sort(a.begin(), a.end());
ll s = 0;
ll ans = 0;
rep(j, n) {
ans += (ll)a[j] * j;
ans -= s;
s += a[j];
}
cout << ans << '\n';
return 0;
}