【深基7.例10】旗鼓相当的对手 - 加强版

题意

给出按字典序排列的学生信息。如果两个学生每一科分差都不超过 5，且总分分差不超过 10，就输出这对学生姓名。输出顺序也要按字典序组合顺序。

思路

输入姓名已经按字典序排列。因此只要按下标枚举 i < j 的学生对，输出顺序就满足题目要求。

把判断封装成函数：

python

1is_close(left, right)

它检查：

三科分差都不超过 5；
总分分差不超过 10。

N <= 1000，枚举所有学生对是 $O(N^2)$ ，可以接受。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：for i in range(n) 与 for j in range(i+1, n) 是枚举无序点对的常用写法。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：元组可保存固定字段记录。
abs(a - b) 计算分差。
把总分和判断逻辑封装成函数，可以让双重循环更清楚。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22def total(student):
    return student[1] + student[2] + student[3]


def is_close(left, right):
    for subject in range(1, 4):
        if abs(left[subject] - right[subject]) > 5:
            return False
    return abs(total(left) - total(right)) <= 10


n = int(input())
students = []

for _ in range(n):
    name, chinese, math, english = input().split()
    students.append((name, int(chinese), int(math), int(english)))

for i in range(n):
    for j in range(i + 1, n):
        if is_close(students[i], students[j]):
            print(students[i][0], students[j][0])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

struct Student {
    char name[15];
    int ch, ma, en, tot;
};

Student stu[1005];
int n;

// 判断两名学生是否为"旗鼓相当的对手"
bool is_close(Student &a, Student &b) {
    if (abs(a.ch - b.ch) > 5) return false;
    if (abs(a.ma - b.ma) > 5) return false;
    if (abs(a.en - b.en) > 5) return false;
    if (abs(a.tot - b.tot) > 10) return false;
    return true;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> stu[i].name >> stu[i].ch >> stu[i].ma >> stu[i].en;
        stu[i].tot = stu[i].ch + stu[i].ma + stu[i].en;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (is_close(stu[i], stu[j]))
                cout << stu[i].name << " " << stu[j].name << "\n";
        }
    }
    return 0;
}

复杂度

枚举所有学生对，时间复杂度是 $O(N^2)$ ，保存学生信息空间复杂度是 $O(N)$ 。

总结

当输入顺序已经满足输出顺序时，不必额外排序。直接按 i < j 枚举学生对，既避免重复，也保证姓名顺序。

【深基7.例10】旗鼓相当的对手 - 加强版

目录

题意

思路

Python 知识

代码

复杂度

总结