题目内容
某团队近期需要组织一支队伍参加拔河比赛，团队共有队员n人，比赛队员人数要求为m人，n>m，n个队员按编号，1到n的顺序参加k轮力量测试，每轮的测试成绩用正整数表示。
根据n个队员的力量测试成绩选择比赛队员m人，先选择k轮测试中最好成绩最大的队员，若有多人的最好成绩相等，则优先选择其中第二好成绩最大的队员，依次类推，最后若还有相等的情况，则优先选择编号较小的队员。每个人只能被选择一次。
输入描述
第1行，团队队员总数n，比赛队员要求的人数m，力量测试轮数k
第i+1行 (i从1到n)，第i个队员参与力量测试第1~k轮的测试成绩，每轮成绩用空格分隔
n,m和k均为正整数，0<m<n<=10^3；0<k<=10^3，0<每轮测试成绩<=10^5
输出描述
按上述选择顺序选出的比赛队员编号的列表，用空格分隔
样例
输入：
4 3 3
10 12 14
11 12 13
12 15 10
12 11 13
输出：3 1 2
解题思路
本题的关键在于对队员进行多维度的排序，以确保按照规定的优先级正确选出比赛队员。首先，对每位队员的k轮测试成绩进行降序排序，确保每个队员的成绩从高到低排列。然后，按照每位队员排序后的成绩列表逐项进行比较，优先选择在各个成绩项上表现更优的队员。如果在所有成绩项上都相同，则优先选择编号较小的队员。通过这种多关键字排序的方法，可以有效地从n名队员中筛选出符合要求的m名比赛队员，保证选择过程符合题目要求的优先级规则。
- 数据预处理：对于每个队员，将其k轮测试成绩排序，降序排列。这样每个队员的成绩列表从最好到最差。
- 排序比较：按照以下优先级对所有队员进行排序：
- 首先比较每个队员的第一个成绩（最好成绩），成绩高者优先。
- 若第一成绩相同，则比较第二个成绩，成绩高者优先。
- 依此类推，直到所有k个成绩都比较完。
- 若所有成绩都相同，则编号小的队员优先。
- 选择队员：排序完成后，选择前m个队员的编号作为比赛队员。
编程实现
C++
#include <bits/stdc++.h>
using namespace std;
// 定义队员结构体
struct Player {
int id; // 队员编号
vector<int> scores; // 排序后的成绩列表
};
// 自定义比较函数
bool comparePlayers(const Player &a, const Player &b) {
// 比较每个成绩
for(int i = 0; i < a.scores.size(); ++i){
if(a.scores[i] != b.scores[i]){
return a.scores[i] > b.scores[i]; // 成绩高者优先
}
}
// 成绩完全相同，比较编号
return a.id < b.id;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k; // 输入n, m, k
vector<Player> players(n);
for(int i = 0; i < n; ++i){
players[i].id = i + 1; // 编号从1开始
players[i].scores.resize(k);
for(int j = 0; j < k; ++j){
cin >> players[i].scores[j]; // 输入每轮成绩
}
// 将成绩排序降序
sort(players[i].scores.begin(), players[i].scores.end(), greater<int>());
}
// 对所有队员排序
sort(players.begin(), players.end(), comparePlayers);
// 输出前m个队员的编号
for(int i = 0; i < m; ++i){
if(i > 0) cout << ' ';
cout << players[i].id;
}
return 0;
}
Python
# 定义队员类
class Player:
def __init__(self, id, scores):
self.id = id
# 排序成绩降序
self.scores = sorted(scores, reverse=True)
# 定义比较函数
def __lt__(self, other):
for a, b in zip(self.scores, other.scores):
if a != b:
return a > b
return self.id < other.id
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
n, m, k = map(int, data[idx:idx+3])
idx +=3
players = []
for i in range(1, n+1):
scores = list(map(int, data[idx:idx+k]))
idx +=k
player = Player(i, scores)
players.append(player)
# 排序
players.sort()
# 输出前m个队员的编号
selected = [str(player.id) for player in players[:m]]
print(' '.join(selected))
if __name__ == "__main__":
main()
Java
import java.util.*;
import java.io.*;
public class Main {
// 定义队员类
static class Player implements Comparable<Player>{
int id;
List<Integer> scores;
Player(int id, List<Integer> scores){
this.id = id;
// 排序降序
Collections.sort(this.scores = scores, Collections.reverseOrder());
}
@Override
public int compareTo(Player other){
for(int i = 0; i < this.scores.size(); i++){
if(!this.scores.get(i).equals(other.scores.get(i))){
return other.scores.get(i) - this.scores.get(i); // 降序
}
}
return this.id - other.id; // 编号升序
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] first = br.readLine().trim().split("\\s+");
int n = Integer.parseInt(first[0]);
int m = Integer.parseInt(first[1]);
int k = Integer.parseInt(first[2]);
List<Player> players = new ArrayList<>();
for(int i=1; i<=n; i++){
String[] line = br.readLine().trim().split("\\s+");
List<Integer> scores = new ArrayList<>();
for(int j=0; j<k; j++) scores.add(Integer.parseInt(line[j]));
players.add(new Player(i, scores));
}
// 排序
Collections.sort(players);
// 输出前m个队员的编号
StringBuilder sb = new StringBuilder();
for(int i=0; i<m; i++){
if(i >0) sb.append(' ');
sb.append(players.get(i).id);
}
System.out.println(sb.toString());
}
}
