P6067题解

· · 题解

题目传送门

思路

拿到这个题，没看 n 我就知道不能用暴力，看样子不能 O(n^2)。

首先，我们可以把题简化一下，第 i 头牛和 j 头牛音量只需要 \mid x_{i}-x_{j}\mid，因为有绝对值，\mid x_{i}-x_{j}\mid 跟 \mid x_{j}-x_{i}\mid 是一样的，所以最后只需乘 2 即可。

于是，我们枚举第 i 头奶牛，算出它与第 1 \backsim i-1 头奶牛谈话的总音量。

咱们再看看这个算第 i 头奶牛总音量的式子。

(a_{i}-a_{i-1})+(a_{i}-a_{i-2})+...+(a_{i}-a_{1})

我们把括号拆开。

a_{i}-a_{i-1}+a_{i}-a_{i-2}+...+a_{i}-a_{1}

这里一共有 i-1 个 a_{i}，于是，我们可以把这个式子简化。

a_{i}*(i-1)-a_{i-1}-a_{i-2}-...-a_{1}

我们把 a_{i-1}-a_{i-2}-...a_{1} 用前缀和存，这样时间复杂度并不会爆。

注意：这种方法必须有序，否则不能变成我们简化后的式子。

话不多说，直接上代码。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long ans,a[1000005],n,sum[1000005];
int main(){
    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++){
        sum[i]=sum[i-1]+a[i];//前缀和 
    }
    for(int i=n;i>=1;i--){
        ans=ans+labs(sum[i-1]-a[i]*(i-1));//简化后的式子 
    }
    cout<<ans*2;//把少计算的补回来 
    return 0;
}