自动搬运

查看原文

来自洛谷，原作者为

	ouhsnaijgnat 资瓷壶关||重回巅峰

搬运于2025-08-24 22:17:05，当前版本为作者最后更新于2022-07-29 14:55:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

拿到这个题，没看 $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;
}