距离之和

题目描述

在一条数轴上有N头牛在不同的位置上，每头牛都计算到其它各头牛的距离。求这n*(n-1)个距离的总和。

输入

1<= N <= 10000。每头牛所在位置是一个范围在0到1,000,000,000之内的整数。

第一行：N

    后面N行，每行一个整数，表示一头牛所在位置。

输出

一个整数。

样例输入

5
1
5
3
2
4

样例输出

40

提示

说明：

（1+2+3+4)+(4+3+2+1)

+(2+1+1+2)+(1+1+2+3)

+(3+2+1+1) = 40

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=(j);i<=(k);++i)
using namespace std;
long long n, a[100001];
long long ans = 0; 
template<class T> inline void read(T &x) {
    x=0;
    register char c=getchar();
    register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    if(f)x=-x;
}
int main() {
    read(n);
    rep(i, 1, n) {
        read(a[i]);
    }
    sort(a + 1, a + 1 + n);
    for (register int i = 1; i < n; i ++) {
        ans += (n - i) * (a[i + 1] - a[i]);
    }
    long long cur = ans;
    for (int i = 2; i <= n; i ++) {
        cur += (a[i] - a[i - 1]) * (i - 1 - (n - i + 1));
        ans = ans + cur;
    }
    cout << ans << endl;
    return 0;
}