【Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)】

题目：


思路：
我们转化问题为每一列的min值和最小
即需要将该排尽可能小的值放到他该放的位置
即我们要每次取所有元素中尽可能小的值放到他这一排的某个位置来盖住这一列别的元素
那么问题来了：我们如何每次找到尽可能小的呢？

这里有一种方式，用一个结构体存所有元素位置和它的值，并对值排序，我们要找的下标就露出来可以让我们用了
然后就是安排位置
我们只需要每次用最小的建立一排“不看该排别的元素”
但是这一排只是虚拟的一排
它并不放到同一排
只是在不看别的元素下的意义上的一排而已

设cnt为0
我的方法是向前填到这一排的cnt位置
同时cnt+1
这样就建立了一排

交换明显是不安全的，容易对排好的元素更改（我的这里fst了）
于是可以使用一个初始化为0的答案矩阵来存放我们建好的排
输出的时候每次如果这个位置被填了，就输出这个位置
否则返回原输入数组中找有没有没有用过的元素，并把这个元素放到这里（元素是谁不影响，因为我们这一排只考虑我们填的最小的）

代码：

//#pragma GCC optimize(3,"Ofast","inline")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define G 10.0
#define LNF 1e18
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long
#define INF 0x7FFFFFFF
#define Regal exit(0)
#define Chivas int main()
#define pb(x) push_back(x)
#define SP system("pause")
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define IOS ios::sync_with_stdio(false)
#define mm(a, b) memset(a, b, sizeof(a))
#define each_cass(cass) for (cin>>cass; cass; cass--)
#define test(a) cout << "---------" << a << "---------" << '\n'
 
using namespace std;
 
struct node{//存输入矩阵的位置对应元素
    ll x;
    ll y;
    ll val;
    friend bool operator < (node a,node b){
        return a.val < b.val;
    }
    friend bool operator == (node a,node b){
        return ((a.x == b.x)&&(a.y == b.y)&&(a.val == b.val));
    }
};
 
inline void solve(){
    ll n, m;
    cin >> n >> m;
    vector<node> stvc;//对所有元素排序
    vector<ll> vec[n + 5];//输入的矩阵
    ll res[n + 5][m + 5];//存放最优位置矩阵
    for(int i = 0; i < n + 5; i ++){
        for(int j = 0; j < m + 5; j ++) res[i][j] = 0;
    }


    for(ll i = 0; i < n; i ++){
        for(ll j = 0;j < m; j ++){
            ll x;
            cin >> x;
            vec[i].push_back(x);
        }
    }


    ll cnt = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            stvc.push_back({i, j, vec[i][j]});
        }
    }


    sort(stvc.begin(), stvc.end());
    while(cnt < m){//从输入矩阵中拿出一个最小的放到答案矩阵里面
        res[stvc[cnt].x][cnt] = stvc[cnt].val;
        vec[stvc[cnt].x][stvc[cnt].y] = 0;
        cnt ++;
    }


    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            if(res[i][j]){//如果这里被放过最小值
                cout << res[i][j] << " ";
            }else{//没被放过就进输入矩阵里面找出来一个随便放进去
                for(int vc_j = 0; vc_j < m; vc_j ++){
                    if(vec[i][vc_j]){
                        cout << vec[i][vc_j] << " ";
                        vec[i][vc_j] = 0;
                        break;
                    }
                }
            }
        }
        cout << endl;
    }
}
Chivas{
    int cass;
    IOS;
    each_cass(cass){
        solve();
    }
    Regal;
}