题解

分析：看了题目发现$n$有$100000$，所以暴力是肯定过不了的，那么我们就可以考虑另一种类似公式递推的方法，我们先对所有牛按照位置进行排序，然后假设$F[i]$表示第i头牛与其他牛交谈发出的总音量，然后对于第$i+1$头牛，我们设一个d值，代表第i头牛与第$i+1$头牛之间的距离，那么对于第$i+1$头牛之前的牛$j$，与第$i+1$头牛交谈产生的音量值就是第i头牛与第j头牛交谈的音量$+d$，同样，对于第$i+1$头牛之后的牛$j$，与第$i+1$头牛交谈产生的音量值就是第$i$头牛与第j头牛交谈的音量-d，所以我们可以得出递推式$F[i+1]=F[i]+d*(i-1)+d*(n-i+1)$，这样$O（n）$递推下去就行了，最后把音量值加起来就是所求的答案了。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=100005;
 
int n;
ll a[maxn]; 
ll f[maxn];
 
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
    scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) {
    f[1]+=a[i]-a[1];
    }
    ll ans=f[1];
    for(int i=2;i<=n;i++) {
    ll d=a[i]-a[i-1];
    f[i]=f[i-1]+d*(i-1)-d*(n-i+1);
        ans+=f[i];
    }
    printf("%lld\n",ans);
    return 0;
}