题目描述
数轴上有N个点，任意两点连线得到n(n-1)条线段，试求线段的总长。
输入
第一行，一个整数N，表示点数。 接下来N行，每行一个整数X_i，表示点的坐标。
输出
一个整数，表示线段的总长。
样例输入
5 1 5 3 2 4
样例输出
40
提示
N < = 10000 , 0 < = X_i < = 1000000000
从X_i看出来，他的数据应该为10^9,所以一定要考虑long long，用上long long后，期初的想法就是扫一遍，然后O（n2）就能结果，当时担心着T，但是没有T，
过了后，又想到了另外一种简单的O（n）算法、先写出来O（n2）的方法了：
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 10000+5
long long a[MAX];
int main(void)
{
int n;
while ( cin>>n )
{
for ( int i = 0;i < n;i++ )
{
cin>>a[i];
}
sort(a,a+n);
long long sum = 0;
for ( int i = 0;i < n-1;i++ )
{
for ( int j = i+1;j < n;j++ )
{
sum+=a[j]-a[i];
}
}
cout<<2*sum<<endl;
}
return 0;
}
O（n）的算法思想就是算排完序后的点对于答案的贡献程度了，并且发现了，第一个点与后面的点的连线对于答案的贡献恰好满足前缀和：
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 10000+5
long long a[MAX];
long long sa[MAX];
int main(void)
{
int n;
while ( cin>>n )
{
for ( int i = 1;i <= n;i++ )
{
cin>>a[i];
}
sort(a+1,a+1+n);
for ( int i = 1;i <= n;i++ )
{
sa[i] = sa[i-1]+a[i];
}
long long sum = 0;
for ( int i = 1;i <= n;i++ )
{
sum+=sa[n]-sa[i-1]-a[i]*(n+1-i);
}
cout<<sum*2<<endl;
}
return 0;
}