较为入门的解决方案

· · 题解

这是鄙人的第一篇题解，用的方法也比较入门，请多关照。

言简意赅的，暴力计算是显然会超时的，又有绝对值的计算，可以先进行排序，再计算其系数并进一步运算，以达到简便运算的目的。

原测评记录。

下面的代码经过整理，思路不变。

#include <iostream>
#include <algorithm>
#define ull unsigned long long
using namespace std;

ull b[300005];
int main()
{
    ull t, n, m, sum;
    cin >> t; // 总组数
    while (t--)
    {
        cin >> n >> m;
        ull a[n + 5][m + 5];
        for (ull i = 1; i <= n; i++)
            for (ull j = 1; j <= m; j++)
                scanf("%llu", &a[i][j]); // 数据读入
        sum = 0; // sum 清零
        for (ull j = 1; j <= m; j++) // 对于每一列
        {
            for (ull i = 1; i <= n; i++)
                b[i] = a[i][j]; // 放到另一个数组中，方便操作
            sort(b + 1, b + 1 + n); // 排序
            for (ull i = 1; i <= n; i++)
                sum = sum + (2 * i - n - 1) * b[i]; // 计算系数并运算
        }
        cout << sum << endl;
    }
    // system("pause");
    return 0;
}

对于系数的计算，个人理解为：

假定有

a_{1}\ \ a_{2}\ \ a_{3}\ \ a_{4}\ \ a_{5}

这样的数组，已经按照升序排列，那么在本题中，有

a_{5}-a_{1}+a_{4}-a_{1}+a_{3}-a_{1}+a_{2}-a_{1}+a_{5}-a_{2}+a_{4}-a_{2}+a_{3}-a_{2}+a_{5}-a_{3}+a_{4}-a_{3}+a_{5}-a_{4}

这样的计算方式。化简后，得

4\times a_{5}+2\times a_{4}+0\times a_{3}-2\times a_{2}-4\times a_{1}

可知 a_{5} 被加了 4 次、a_{4} 被加了 3 次又减了 1 次……可以发现，被加的次数为 i-1，被减的次数为 n-i，可得

a_{i}\times((i-1)-(n-i)) \text{当前数字}\times(\text{被加次数}-\text{被减次数})

那么

\text{原式}=\sum_{i=1}^{n}a_{i}\times(2\times i-n-1)

大致就是这样吧。

以及，非常荣幸这道题采用了小生的翻译。