题目描述

难度分:$1200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n \times m$之和$\leq 2 \times 10^5$。

每组数据输入$n$，$m(1 \leq n \times m \leq 2 \times 10^5)$和$n$个长为$m$的数组，元素范围$[1,10^6]$。

把这$n$个数组重新排列（数组内部的元素不能重排），拼接成一个长为$n \times m$的数组$A$。

设$A$的前缀和数组为$pre$。输出$sum(pre)$的最大值。

输入样例

3
2 2
4 4
6 1
3 4
2 2 2 2
3 2 1 2
4 1 2 1
2 3
3 4 5
1 1 9

输出样例

41
162
72

算法

排序+贪心

直觉上感觉$pre$中大的元素越早出现越好，而数组内部不允许重排，所以直接按照每个数组的累加和进行排序，将累加和大的排在前面。这样就得到了数组$A$的排列顺序，然后遍历$n$个数组一边计算$A$的前缀和$sum$，一边把$sum$累加到答案上即可。

复杂度分析

时间复杂度

比较两个数组的时候时间复杂度为$O(m)$，加上排序的时间复杂度$O(nlog_2n)$，将所有数组按照累加和大小排序的时间复杂度为$O(mnlog_2n)$。最后求答案只要把这些数组遍历一遍就好了，时间复杂度为$O(nm)$。因此，整个算法的时间复杂度为$O(nmlog_2n)$。

空间复杂度

除了输入的$n$个数组，空间复杂度的消耗在于排序，以快排为基准，额外空间复杂度为$O(log_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<vector<int>> arrs;
        for(int i = 0; i < n; i++) {
            vector<int> arr;
            for(int j = 0; j < m; j++) {
                int val;
                scanf("%d", &val);
                arr.push_back(val);
            }
            arrs.push_back(arr);
        }
        sort(arrs.begin(), arrs.end(), [&](auto&a, auto&b) {
            return accumulate(a.begin(), a.end(), 0LL) > accumulate(b.begin(), b.end(), 0LL);
        });
        long long ans = 0, sum = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                sum += arrs[i][j];
                ans += sum;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}