https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_c
解説
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/submissions/3664421
競プロでよくあるテクとして、「絶対値は扱いにくいので場合分けして消す」というのがある。
これもその方針でやる。
まず、xを昇順ソートする。
ある座標x[i]があったときに、それよりも前の座標との交流コストは、全てx[i]よりも小さいので、
(x[i]-x[i-1]) + (x[i]-x[i-2]) + (x[i]-x[i-3]) + ... + (x[i] - x[0])
となる。これを変形すると、
x[i] * i - (x[i - 1] + x[i - 2] + x[i - 3] + ... + x[0])
となる。
なので、今までの個数cnt(これがx[i]*iのiになる)と
今までの総和sm(これが(x[i - 1] + x[i - 2] + x[i - 3] + ... + x[0])になる)を保持しながら、交流コストの総和を取ると答え。
int N, X[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> X[i]; sort(X, X + N); ll sm = 0, cnt = 0; ll ans = 0; rep(i, 0, N) { ans += cnt * X[i] - sm; sm += X[i]; cnt++; } cout << ans << endl; }