题解

题目描述：

有 M 个评委对 N 个选手进行评分，评分范围从 1 到 10。每个评委给每个选手打分，且每个评委的评分矩阵已给出。需要根据评分规则，输出得分最多的前三名选手的编号。如果得分相同，则得分高分值最多的选手排名靠前（即先比较 10 分的个数，再比较 9 分的个数，依此类推）。

输入：

• 第一行包含两个整数 M 和 N，表示评委的数量和选手的数量。
• 接下来 M 行，每行包含 N 个整数，表示每个评委对每个选手的评分。
• 分数范围是 1 到 10。

输出：

• 输出前三名选手的编号（从1开始）。

约束：

• 3 <= M <= 10
• 3 <= N <= 100
• 每个分数在 1 到 10 之间。

解题思路：

1. 输入解析：

   • 第一行解析 M 和 N，分别表示评委数量和选手数量。若不符合约束条件，立即输出 -1。
   • 接下来读取每个评委的评分，存入二维数组 scores 中。

2. 计算每个选手的得分情况：

   • 对每个选手计算总分，并统计每个分数（1分到10分）的频次。
   • 将每个选手的编号与其得分和得分频率存储为一个 pair<int, vector<int>> 对象。int 存储选手编号，vector<int> 存储总分和频率统计。

3. 排序：

   • 根据总分进行排序，若总分相同，则按照每个分数的频率进行排序。排序规则：首先比较总分，若相同则依次比较 10 分、9 分、8 分、... 的频率。

4. 输出前三名：

   • 排序后输出前三名选手的编号。

复杂度分析：

• 时间复杂度：

  • 读取输入：O(M * N)
  • 计算每个选手的得分：O(M * N)
  • 排序：O(N log N)

  总体复杂度为 O(M * N + N log N)。

• 空间复杂度：

  • O(M * N) 用于存储评分矩阵。
  • O(N) 用于存储选手的得分信息。

代码实现：

C++

#include <bits/stdc++.h>
using namespace std;

// 解析输入的逗号分隔的整数
vector<int> parseLine(const string& line) {
vector<int> result;
    stringstream ss(line);
    string token;
    while (getline(ss, token, ',')) {
        result.push_back(stoi(token)); // 将每个分割出来的字符串转成整数
    }
    return result;
}

// 排序函数，首先按总分排序，如果总分相同则按每个分数的频率排序
bool compare(const pair<int, vector<int>>& a, const pair<int, vector<int>>& b) {
    if (a.second[0] != b.second[0]) return a.second[0] > b.second[0]; // 比较总分
    for (int i = 10; i >= 1; --i) { // 如果总分相同，比较各分数的频率
        if (a.second[i] != b.second[i]) return a.second[i] > b.second[i];
    }
    return false;
}

int main() {
    string firstLine;
    getline(cin, firstLine); // 读取第一行输入

    // 解析第一行，获取 M 和 N
    vector<int> firstParams = parseLine(firstLine);
    if (firstParams.size() != 2) {
        cout << -1 << endl; // 输入格式异常
        return 0;
    }

    int M = firstParams[0]; // 评委人数
    int N = firstParams[1]; // 选手人数

    // 检查 M 和 N 是否符合范围
    if (M < 3 || M > 10 || N < 3 || N > 100) {
        cout << -1 << endl; // M 或 N 不合法
        return 0;
    }

    vector<vector<int>> scores(M, vector<int>(N));

    // 读取 M 行评分
    for (int i = 0; i < M; ++i) {
        string line;
        getline(cin, line); // 读取每行评分
        vector<int> row = parseLine(line);
        
        if (row.size() != N) {
            cout << -1 << endl;
            return 0;
        }
        
        for (int j = 0; j < N; ++j) {
            if (row[j] < 1 || row[j] > 10) { // 分数不合法
                cout << -1 << endl;
                return 0;
            }
            scores[i][j] = row[j]; // 存储评分
        }
    }

    // 存储每个选手的总分和分数频率
    vector<pair<int, vector<int>>> players;
    for (int j = 0; j < N; ++j) {
        int totalScore = 0;
        vector<int> scoreFreq(11, 0); // scoreFreq[0] 存储总分，scoreFreq[1]~scoreFreq[10] 存储每个分数的频率

        for (int i = 0; i < M; ++i) {
            int score = scores[i][j];
            totalScore += score; // 累加总分
            scoreFreq[score]++; // 更新分数频率
        }

        scoreFreq[0] = totalScore; // 存储总分
        players.emplace_back(j + 1, scoreFreq); // 存储选手编号及分数信息
    }

    // 排序选手
    sort(players.begin(), players.end(), compare);

    // 输出前3名选手的编号
    cout << players[0].first << "," << players[1].first << "," << players[2].first << endl;

    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String firstLine = scanner.nextLine();
        String[] firstParams = firstLine.split(",");
        
        int M = Integer.parseInt(firstParams[0]);
        int N = Integer.parseInt(firstParams[1]);
        
        if (M < 3 || M > 10 || N < 3 || N > 100) {
            System.out.println(-1);
            return;
        }
        
        int[][] scores = new int[M][N];
        
        // 读取评分矩阵
        for (int i = 0; i < M; i++) {
            String line = scanner.nextLine();
            String[] row = line.split(",");
            if (row.length != N) {
                System.out.println(-1);
                return;
            }
            
            for (int j = 0; j < N; j++) {
                int score = Integer.parseInt(row[j]);
                if (score < 1 || score > 10) {
                    System.out.println(-1);
                    return;
                }
                scores[i][j] =

 score;
            }
        }
        
        List<Player> players = new ArrayList<>();
        
        for (int j = 0; j < N; j++) {
            int totalScore = 0;
            int[] scoreFreq = new int[11];
            for (int i = 0; i < M; i++) {
                int score = scores[i][j];
                totalScore += score;
                scoreFreq[score]++;
            }
            players.add(new Player(j + 1, totalScore, scoreFreq));
        }
        
        // 排序
        players.sort((a, b) -> {
            if (b.totalScore != a.totalScore) {
                return Integer.compare(b.totalScore, a.totalScore);
            }
            for (int i = 10; i >= 1; i--) {
                if (b.scoreFreq[i] != a.scoreFreq[i]) {
                    return Integer.compare(b.scoreFreq[i], a.scoreFreq[i]);
                }
            }
            return 0;
        });
        
        // 输出前三名
        System.out.println(players.get(0).id + "," + players.get(1).id + "," + players.get(2).id);
    }

    static class Player {
        int id;
        int totalScore;
        int[] scoreFreq;

        Player(int id, int totalScore, int[] scoreFreq) {
            this.id = id;
            this.totalScore = totalScore;
            this.scoreFreq = scoreFreq;
        }
    }
}

Python

def parse_line(line):
    # 解析每行输入，返回一个由逗号分隔的整数列表
    return list(map(int, line.split(',')))

def compare(a, b):
    # 比较两个选手的得分和频率
    # 首先比较总分 (a[1][0] 和 b[1][0] 分别是总分)
    if a[1][0] != b[1][0]:
        return b[1][0] - a[1][0]  # 总分较高的选手排前
    
    # 如果总分相同，依次比较每个分数的频率（10分到1分）
    for i in range(10, 0, -1):
        if a[1][i] != b[1][i]:
            return b[1][i] - a[1][i]  # 频率较高的分数排前
    return 0  # 如果总分和所有分数频率完全相同，返回0

def main():
    # 读取第一行输入，包含M和N
    first_line = input()
    M, N = map(int, first_line.split(','))  # 评委人数M和选手人数N

    # 如果M或N不符合题目要求，直接输出-1
    if M < 3 or M > 10 or N < 3 or N > 100:
        print(-1)
        return

    scores = []  # 存储所有评委的评分数据

    # 读取M行评委评分数据
    for _ in range(M):
        line = input()  # 每行表示一个评委的评分
        row = parse_line(line)  # 将逗号分隔的字符串转为整数列表
        
        # 如果该行的选手数量与N不匹配，输出-1
        if len(row) != N:
            print(-1)
            return
        
        # 如果有评分不在合法范围(1-10)，也输出-1
        if any(s < 1 or s > 10 for s in row):
            print(-1)
            return
        
        scores.append(row)  # 存储当前评委的评分数据

    players = []  # 存储每个选手的总分和每个分数的频率

    # 计算每个选手的总分以及各个分数的频率
    for j in range(N):
        total_score = sum(scores[i][j] for i in range(M))  # 计算该选手的总分
        score_freq = [0] * 11  # 用一个列表记录每个分数的频率 (score_freq[0] 是总分)
        
        # 计算该选手的每个分数的频率
        for i in range(M):
            score_freq[scores[i][j]] += 1
        
        score_freq[0] = total_score  # 将总分放入score_freq[0]的位置
        players.append((j + 1, score_freq))  # 选手编号从1开始，存储选手编号和其分数频率

    # 按照自定义规则对选手进行排序
    players.sort(key=lambda x: (x[1][0], *x[1][1:]), reverse=True)
    # 排序规则：先按总分排序，如果总分相同，按每个分数的频率（10分到1分）排序

    print(f"{players[0][0]},{players[1][0]},{players[2][0]}")

# 调用主函数
if __name__ == "__main__":
    main()

题目描述

一共有 $N$ 个选手参加比赛，选手编号为 $1$ ~ $N$（$3<=N<=100$），有 $M$（$3<=M<=10$）个评委对选手进行打分。

打分规则为每个评委对选手打分，最高分 $10$ 分，最低分 $1$ 分。

请计算得分最多的 $3$ 位选手的编号。 如果得分相同，则得分高分值最多的选手排名靠前

($10$ 分数量相同，则比较 $9$ 分的数量，以此类推，用例中不会出现多个选手得分完全相同的情况)。

输入描述

第一行为半角逗号分割的两个正整数，第一个数字表示$M$（$3<=M<=10$）个评委，第二个数字表示 $N$（$3<=N<=100$）个选手。

第 $2$ 到 $M+1$ 行是半角逗号分割的整数序列，表示评委为每个选手的打分，$0$ 号下标数字表示 $1$ 号选手分数，$1$ 号下标数字表示 $2$ 号选手分数，依次类推。

输出描述

选手前 $3$ 名的编号。

注：若输入为异常，输出 $-1$ ，如 $M$、$N$、打分不在范围内。

样例1

输入

4,5
10,6,9,7,6
9,10,6,7,5
8,10,6,5,10
9,10,8,4,9

输出

2,1,5

说明

第一行代表有 $4$ 个评委， $5$ 个选手参加比赛

矩阵代表是 $4$ * $5$，每个数字是选手的编号，每一行代表一个评委对选手的打分排序，

$2$ 号选手得分 $36$ 分排第 $1$ ，

$1$ 号选手 $36$ 分排第 $2$ ，

$5$ 号选手 $30$ 分

($2$ 号 $10$ 分值有 $3$ 个，$1$ 号 $10$ 分值只有 $1$ 个，所以 $2$ 号排第一)

样例2

输入

2,5
7,3,5,4,2
8,5,4,4,3

输出

-1

说明

只有 $2$ 个评委，要求最少为 $3$ 个评委

样例3

输入

4,2
8,5
5,6
10,4
8,9

输出

-1

说明

只有 $2$ 名选手参加，要求最少为 $3$ 名

样例4

输入

4,5
11,6,9,7,8
9,10,6,7,8
8,10,6,9,7
9,10,8,6,7

输出

-1

说明

第一个评委给第一个选手打分 $11$ ，无效分数