题解：AT_abc351_f [ABC351F] Double Sum

· · 题解

题目大意

还用说吗？就是求下面这个式子的值啊！

\sum_{i=1}^{N}\sum_{j=i+1}^{N}\max(A_j-A_i,0)

题目思路

首先，把式子转化一下：因为 0 可以转化为 A_j-A_j 所以式子转化为：

\sum_{i=1}^{N}\sum_{j=i+1}^{N}\max(A_j-A_i,A_j-A_j)

然后提一个 A_j 出来，就是：

\sum_{i=1}^{N}\sum_{j=i+1}^{N}A_j+\max(-A_i,-A_j)

再将负数转化为正数，也就是将 \max 内的 -A_i 和 -A_j 变为 A_i 和 A_j。因为从负数化成了正数，所以前面的符号也要变，不是加了，是减。因为负数的时候取的是 \max，也就是去掉负号后更小的那个数。所以将负号去掉后就不是取 \max 了，而是取 \min。式子为：

\sum_{i=1}^{N}\sum_{j=i+1}^{N}A_j-\min(A_i,A_j)

最后我们再来考虑计算的问题。

先考虑 A_j。因为第 j 个数，会跟前面的 j-1 个数都匹配一遍，所以第 j 个数会贡献出 A_j \times (j-1)。

再考虑 -\min(A_i,A_j)。因为每两个数之间一定会匹配一次，所以第 i 小的数会贡献出 -A_i \times (n-i)。

所以我们只需要先计算一遍所有 A_j 的贡献，再排一遍序，在计算一下所有第 i 小的贡献就可以通过这道题啦！

Code

#include<bits/stdc++.h>
using namespace std;
long long n,ans,a[400010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],ans+=a[i]*(i-1);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)ans-=a[i]*(n-i);
    cout<<ans;
    return 0;
}