急解编程
题目描述
在一条数轴上有N头牛在不同的位置上，每头牛都计算到其它各头牛的距离。求这n*(n-1)个距离的总和。
数据范围
....每头牛所在位置是一个范围在0到1,000,000,000之内的整数。
输入文件
第一行：N
后面N行，每行一个整数，表示一头牛所有位置。
输出文件
一个整数。
输入样例
515324
输出样例
40
样例说明
（1+2+3+4)+(4+3+2+1)+(2+1+1+2)+(1+1+2+3)+(3+2+1+1)=40
上面的很容易，可n开到1000000简直要我命呀;。
哪位可以帮帮我;
最佳答案
这个是2009南海区集训队初中选拔题,网上搜一堆的,以下是其中之一
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 1e4+10;
int n;
LL a[MAXN];
LL dis[MAXN];
LL ans = 0;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
sort(a+1,a+1+n);
dis[1] = 0;dis[2] = a[2]-a[1];
for (int i = 3;i <= n;i++)
{
dis[i] = dis[i-1]+(i-2)*(a[i]-a[i-1]);
dis[i]+=a[i]-a[i-1];
}
for (int i = 1;i <= n;i++)
ans+=dis[i];
cout << ans*2<<endl;
return 0;
}
其他回答
暂无其它回答!
