当前位置: 代码迷 >> 综合 >> codeforces 1517B Morning Jogging
  详细解决方案

codeforces 1517B Morning Jogging

热度:53   发布时间:2023-12-02 23:26:13.0

链接:

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;
}

  相关解决方案