題目：
思路：
我們轉化問題為每一列的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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/280221.html
標籤：其他
下一篇：自定義控制元件-時間軸