JYM 的公司

2019-02-24 15:38:38


题目大意

给出n(n<=500000)个数,求所有数对两个数的差值总和

解法

把n个数排序,然后瞎搞

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<algorithm>
#define int long long
using namespace std;
int n,sum=0,res=0;
int a[500100];
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        res+=a[i]-a[1];
    sum=res;
    for(int i=2;i<=n;i++)
        res=res+(a[i]-a[i-1])*(2*i-n-2),sum+=res;//其实是+(a[i]-a[i-1])*(i-1)-(a[i]-a[i-1])*(n-i+1)
    printf("%lld",sum);
    return 0;
}