G4028 [GESP202609 四级] 有序网格 题解

知识点：二维数组、排序、模拟。

解题思路

先把每一行升序排序，再对每一列升序排序。

为什么正确

相邻两列逐行满足左值不大于右值，因此两列各自排序后的第k小值仍保持此关系；列排序不会破坏行的非递减性。

易错点

第二步只重新排列各列；需同时说明行与列都最终有序，而不只检查列。

复杂度

时间O(nm log m+mn log n)，空间O(nm)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>a(n,vector<int>(m));
    for(auto &row:a) {
        for(int &x:row)cin>>x;
        sort(row.begin(),row.end());
    }
    for(int j=0;j<m;j++) {
        vector<int>v;
        for(int i=0;i<n;i++)v.push_back(a[i][j]);
        sort(v.begin(),v.end());
        for(int i=0;i<n;i++)a[i][j]=v[i];
    }
    for(auto row:a) {
        for(int x:row)cout<<x<<" ";
        cout<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。