start 题解

· · 个人记录

排序

首先看到绝对值我们就可以先想到排序，排序之后就不需要判断绝对值了。

其次我们是不需要有顺序，只要把每一个科目放在一起就可以了。

那么我们就可以得出下式

\sum_i^m[(\sum_j[a_j > a_i]a_j-a_i\times\sum_j[a_j > a_i])+(a_i\times\sum_j[a_j < a_i]-\sum_j[a_j < a_i]a_j)]

这就完了？不。

通过排列组合我们知道，以上是

A^2_n

也就是说每两个人之间就被求两次

而我们只需要求一次就够了，也就是

C^2_n

高出一倍，所以我们就要 \div2。

优化——前缀和

$\sum_{j=1}^ia_j$ 与 $\sum_{j=i+1}^na_j$ 。 而看到这个形式我们必定会想起前缀和。 之后 $\sum_j[a_j > a_i]=i - 1,\sum_j[a_j < a_i]=n-i

推出来式子我们就可以写代码了。

My Code


#include<bits/stdc++.h>
using namespace std;

int a[2010][2010],sum[2010][2010];
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            scanf("%d",&a[j][i]);//保证同一门在一起 
        }
    }
    for(int j = 1;j <= m;j++){
        sort(a[j] + 1,a[j] + 1 + n);//排序 
    } 
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            sum[i][j] = sum[i][j - 1] + a[i][j];//前缀和 
        }
    }
    int ans = 0;
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++){
            ans += (sum[i][n] - sum[i][j] - a[i][j] * (n - j)) + (a[i][j] * (j - 1) - sum[i][j - 1]);
        }
    }
    cout<<ans/2;
}