题解：乒乓球赛代表选拔

题目描述

实验室的学生进行单循环赛，每对选手进行五局三胜制比赛。矩阵中 $a[i][j]$ 表示第 $i$ 个学生在与第 $j$ 个学生的比赛中赢的局数。其中，若 $i ≠ j$，则 $a[i][j]$ 和 $a[j][i]$ 中恰好一个为 $3$（表示获胜），另一个为$0$、$1$ 或 $2$（表示失败）。要求找出赢得比赛最多的学生编号，若有平局则选择编号最小的。

解题思路

1. 问题分析：

   • 每个学生的胜利次数等于其所在行中值为 $3$ 的元素个数（因为 $a[i][j] = 3$ 表示第 $i$ 个学生击败第 $j$ 个学生）。
   • 需遍历矩阵，统计每个学生的胜利次数，然后找出次数最多且编号最小的学生。

2. 算法步骤：

   • 输入矩阵：读取学生人数 $n$ 和 $n×n$ 的比赛结果矩阵。
   • 统计胜利次数：对每个学生 $i$，遍历其所在行，统计值为 $3$ 的元素个数，记为 $sum$。
   • 更新最大值和最小编号：比较当前学生的胜利次数 $sum$ 与全局最大值 $max$。若 $sum$ 更大，则更新 $max$ 和对应的学生编号 $maxIndex$；若 $sum$ 相等，则保留较小的编号（因为遍历顺序是按编号从小到大，先出现的同分数学生编号更小）。

3. 复杂度分析：

   • 时间复杂度：遍历矩阵的时间为 $O(n²)$，其中 $n ≤ 100$，因此算法效率极高。
   • 空间复杂度：仅使用常数额外空间存储统计变量，空间复杂度为 $O(1)$。

代码实现

#include <iostream>
using namespace std;

int main() {
    int n;
    int a[105][105]; // 存储比赛结果矩阵，n最多100，下标0~n-1对应学生1~n
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    
    int maxIndex = 0; // 记录胜利最多的学生编号（初始为0，对应学生1）
    int maxWin = 0;   // 记录最大胜利次数
    
    for (int i = 0; i < n; i++) {
        int winCount = 0; // 当前学生i的胜利次数
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 3) {
                winCount++;
            }
        }
        // 更新最大值和最小编号（若胜利次数相同，先出现的i更小，无需额外处理）
        if (winCount > maxWin) {
            maxWin = winCount;
            maxIndex = i;
        }
    }
    // 输出编号（i从0开始，对应学生i+1）
    cout << maxIndex + 1 << endl;
    return 0;
}