E距离之和【noip模拟赛2】

发表于 | 分类于 ， | 阅读量 次

描述

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

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

输入

第一行：N

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

输出

一个整数。

输入样例 1

5 1
5 3
2
4

输出样例 1

40

说明：
（1+2+3+4)+(4+3+2+1)
+(2+1+1+2)+(1+1+2+3)
+(3+2+1+1) = 40

来源：
来自 <http://www.dingbacode.com/contest/19/problem/E>

题解：
左右距离相加

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

long long d[10010];
long long cha[10010];
long long  a[10010],b[10010];


int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    sort(d+1,d+1+n);
    for(int i=1;i<n;i++)
        cha[i]=d[i+1]-d[i];

    for(int i=1;i<=n;i++)
        {a[i]=(i-1)*(n-i+1)*cha[i-1];}

    for(int j=n;j>=1;j--)
        {b[j]=(n-j+1)*(j-1)*cha[j-1];}


    long long ans=0;
    for(int i=1;i<=n;i++)
    ans+=a[i]+b[i];
    cout<<ans<<endl;

    return 0;
}