链接:
https://codeforces.com/problemset/problem/1517/B
题意:
本题讲的大概是,有n个检查点,每个检查点间有m条路,m名跑者需要从n个检查点中逐个跑过,每名跑者要在m条路中选择一条,并且每条路有且仅有一名跑者选择。每名跑者的疲劳度是跑过所有路中,最短的一条耗费的疲劳度,即该路的长度。求所有跑者疲劳度之和最短的组合。要求任意输出一种即可。
input
2 2 3 2 3 4 1 3 5 3 2 2 3 4 1 3 5
output
2 3 4 5 3 1 2 3 4 1 3 5
我们可以将所有路的长度存入一个数组,取最小的m个,分配给每个运动员。
代码如下:
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
int ans[103][103];
bool isswaped[103][103];
int mn[10003];
int main() {int T;cin >> T;while (T--) {memset(ans, 0, sizeof(ans));memset(isswaped, 0, sizeof(isswaped));memset(mn, 0, sizeof(mn));int n, m;cin >> n >> m;int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> ans[i][j];mn[cnt++] = ans[i][j];}} sort(mn, mn + m*n);//升序排序cnt = m;while (cnt--) {bool f = false;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mn[cnt] == ans[i][j] && !isswaped[i][j]) {//判断它在数组的哪个位置,并且要没有被交换过swap(ans[i][j], ans[i][cnt]);isswaped[i][cnt] = 1;f = true;break;}}if (f) {break;}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << ans[i][j] << " ";}cout << endl;}}return 0;
}