RT

#include <bits/stdc++.h>

using namespace std;

const int N = 150005, M = 4;
struct Block{
    int data[M];
    inline int& operator[](int x) {
        return data[x];
    }
};
Block a[N];
int T, k, n, realAns, ans;
int maxx[M], minn[M];

int main() {
    freopen("lock.in", "r", stdin);
    freopen("lock.out", "w", stdout);
    scanf("%d%d", &T, &k);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < k; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &a[j][i]);
            }
        }
        realAns = INT_MAX;
        for(int Q = 1; Q <= 300; Q++) {
            random_shuffle(a + 1, a + 1 + n);
            ans = 0;
            for(int i = 0; i < k; i++) maxx[i] = minn[i] = a[1][i];
            for(int i = 2; i <= n; i++) {
                int minAns = INT_MAX, minDelta = -1;
                for(int delta = 0; delta < k; delta++) {
                    int tmpAns = ans;
                    for(int j = 0; j < k; j++) {
                        if(a[i][j] > maxx[(j + delta) % k] && a[i][j] - minn[(j + delta) % k] > tmpAns) tmpAns = a[i][j] - minn[(j + delta) % k];
                        if(a[i][j] < minn[(j + delta) % k] && maxx[(j + delta) % k] - a[i][j] > tmpAns) tmpAns = maxx[(j + delta) % k] - a[i][j];
                    }
                    if(tmpAns < minAns) minAns = tmpAns, minDelta = delta;
                }
                // printf("minDelta[%d]->%d\n", i, minDelta);
                ans = minAns;
                for(int j = 0; j < k; j++) {
                    if(a[i][j] > maxx[(j + minDelta) % k]) maxx[(j + minDelta) % k] = a[i][j];
                    if(a[i][j] < minn[(j + minDelta) % k]) minn[(j + minDelta) % k] = a[i][j];
                }
            }
            realAns = min(realAns, ans);
        }
        printf("%d\n", realAns);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

一个基础$O(n)\ \text{dp}$,正确性跟顺序有关