はまやんはまやんはまやん

hamayanhamayan's blog

Pair Distance [CODE THANKS FESTIVAL 2018 C]

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;
}