【结构体与多关键字排序】GESP四级 / CSP-J 题解：luogu-P1093 [NOIP2007 普及组] 奖学金

NOIP 2007 普及组第一题，洛谷 P1093。本题是青少年信息学奥赛与编程等级考试中学习**结构体（struct）与多关键字排序（Multi-key Sorting）**的标志性入门经典试题，被标准收录于 CCF GESP 四级认证考纲（结构体与排序考点）及 CSP-J 普及组核心必做题单。题目重点考察结构体定义、数据复合封装、多级降序/升序比较函数构造，以及严格弱序（Strict Weak Ordering）规范。题目难度⭐⭐☆☆☆，洛谷难度等级评定为普及-。

P1093 [NOIP2007 普及组] 奖学金

🔗 洛谷原题传送门：luogu-P1093 [NOIP2007 普及组] 奖学金

题目要求

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名学生的学号和总分。注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：

7 279
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、$5$ 号。这两名同学的总分都是 $279$（总分等于输入的语文、数学、英语三科成绩之和），但学号为 $7$ 的学生语文成绩更高一些。如果你的前两名的输出数据是：

5 279
7 279

则按输出错误处理，不能得分。

输入格式

共 $n+1$ 行。

第 $1$ 行为一个正整数 $n$（$n \le 300$），表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1 \sim n$（恰好是输入数据的行号减 $1$）。

所给的数据都是正确的，不必检验。

输出格式

共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

输入输出样例 #1

样例输入 #1

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出 #1

6 265
4 264
3 258
2 244
1 237

输入输出样例 #2

样例输入 #2

8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出 #2

8 265
2 264
6 264
1 258
5 258

说明/提示

对于 $100\%$ 的数据，$5 \le n \le 300$，每个科目的成绩均在 $[0, 100]$ 之间。

【题目来源】

NOIP 2007 普及组第一题

题目深度剖析

1. 结构体与数据复合建模

每个学生实体包含多项相互绑定的属性：

• 学号（id）：在输入时按照顺序由 $1$ 编号至 $n$，在排序后必须能准确定位原学生；
• 三门单科成绩（chinese, math, english）：单科取值范围 $[0, 100]$；
• 总分（total）：三科成绩求和，最大为 $100 \times 3 = 300$。

若使用彼此分散的独立数组（如 int id[305], int chinese[305], int total[305]），在执行排序元素交换时极易出现多数组不同步的灾难性 Bug。在 C++ 中，定义 struct Student 结构体能将一个学生的所有字段打包为单个内存实体，无论是直接传参、赋值还是排序交换，都天然保持原子性与一致性。

2. 多关键字排序逻辑与优先级层次

题目给出了明确的三级决胜（Tie-breaking）条件，排序比较器函数 cmp(a, b) 必须按由主到次的规则依序判定：

1. 第一主关键字：总分降序
   若两个学生的 total 不相等，总分更高者优先排前（即 a.total > b.total）；
2. 第二关键字：语文成绩降序
   若总分相同（a.total == b.total），比较单科语文，语文分数高者优先排前（即 a.chinese > b.chinese）；
3. 第三关键字：学号升序
   若总分与语文均相同，比较两人的初始学号，学号更小者优先排前（即 a.id < b.id）。

3. 严格弱序（Strict Weak Ordering）规范

C++ 标准库中的 std::sort 底层基于内省排序（Introsort），要求传入的二元比较谓词必须严格满足数学上的严格弱序：

• 非自反性：cmp(x, x) 必须恒为 false；
• 非对称性：若 cmp(x, y) 为 true，则 cmp(y, x) 必为 false；
• 传递性：若 cmp(x, y) 为 true 且 cmp(y, z) 为 true，则 cmp(x, z) 必为 true。

高频避坑：绝不可写成 >= 或 <=！如果比较逻辑写成 a.total >= b.total，当两元素相等时 cmp(a, a) 将返回 true，破坏非自反性，导致 std::sort 迭代器越界发生段错误（Segmentation Fault）。必须使用严格的大于 > 或小于 <。

解题步骤与核心避坑指南

1. 学号的正确初始化与维护

学号并不是从键盘输入的属性，而是学生在输入序列中的行序（$1 \sim n$）：

for (int i = 0; i < n; ++i) {
    stu[i].id = i + 1; // 从 1 开始编号
    cin >> stu[i].chinese >> stu[i].math >> stu[i].english;
    stu[i].total = stu[i].chinese + stu[i].math + stu[i].english;
}

2. 全局固定数组防越界，杜绝变长数组（VLA）

本题数据规模 $n \le 300$：

• 根据 CCF GESP 与信息学奥赛规范，严禁在函数内使用局部动态变长数组 Student stu[n];；
• 规范做法是定义常量 const int MAXN = 305; 并在全局区声明静态数组 Student stu[MAXN];。

3. 输出前 5 名边界保障

题目要求输出前 $5$ 名学生的学号和总分。在标准测试中 $n \ge 5$，为保证极端测试下的稳健性，可使用 min(n, 5) 作为输出循环上限：

int print_count = min(n, 5);
for (int i = 0; i < print_count; ++i) {
    cout << stu[i].id << " " << stu[i].total << "\n";
}

完整参考代码 (C++)

/**
 * Problem: luogu P1093 [NOIP2007 普及组] 奖学金
 * Algorithm: 结构体与多关键字排序
 * GESP Level: 四级 (CSP-J 基础)
 * Author: OneCoder
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 1. 定义学生结构体，集中封装学号、各科成绩与总分
struct Student {
    int id;       // 学生学号 (1 ~ n)
    int chinese;  // 语文单科成绩
    int math;     // 数学单科成绩
    int english;  // 英语单科成绩
    int total;    // 三科总分
};

// 2. 自定义多关键字比较函数
// 遵循严格弱序规范 (Strict Weak Ordering)，严禁使用 >= 或 <=
bool cmp(const Student &a, const Student &b) {
    // 优先级 1：总分降序 (总分高的排在前面)
    if (a.total != b.total) {
        return a.total > b.total;
    }
    // 优先级 2：若总分相同，语文成绩降序 (语文高的排在前面)
    if (a.chinese != b.chinese) {
        return a.chinese > b.chinese;
    }
    // 优先级 3：若总分和语文成绩均相同，学号升序 (学号小的排在前面)
    return a.id < b.id;
}

// 3. 全局静态数组，避免局部栈溢出与变长数组 (VLA)
const int MAXN = 305;
Student stu[MAXN];

int main() {
    // 基础输入输出流加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }

    // 读入每个学生的各科成绩并计算总分
    for (int i = 0; i < n; ++i) {
        stu[i].id = i + 1; // 依输入顺序标记学号 1 ~ n
        cin >> stu[i].chinese >> stu[i].math >> stu[i].english;
        stu[i].total = stu[i].chinese + stu[i].math + stu[i].english;
    }

    // 调用 STL 快速排序进行多关键字排布，复杂度 O(n log n)
    sort(stu, stu + n, cmp);

    // 依次输出排名前 5 名学生的学号与总分
    int print_count = min(n, 5);
    for (int i = 0; i < print_count; ++i) {
        cout << stu[i].id << " " << stu[i].total << "\n";
    }

    return 0;
}

复杂度深度分析

• 时间复杂度：
  • 数据读入：单层循环遍历 $n$ 个学生，耗时 $\mathcal{O}(n)$；
  • 多关键字排序：采用 std::sort 对包含 $n$ 个元素的结构体数组排序。单次比较耗时为 $\mathcal{O}(1)$，整体排序复杂度为 $\mathcal{O}(n \log n)$；
  • 结果输出：固定输出 $5$ 次，耗时 $\mathcal{O}(1)$；
  • 综合时间复杂度为 $\mathcal{O}(n \log n)$。在最坏规模 $n = 300$ 时，$300 \log_2 300 \approx 2500$ 次运算，耗时 $< 1\text{ ms}$，瞬时完成。
• 空间复杂度：
  • 全局静态数组大小为 $305 \times \text{sizeof(Student)} = 305 \times 20\text{ B} \approx 6.1\text{ KB}$；
  • 空间复杂度为 $\mathcal{O}(n)$，远低于题目的 $128\text{ MB}$ 限制。

总结与同类考点拓展

“奖学金”是多关键字排序的黄金模板题。解决此类问题的核心方法论可归纳为：

1. 结构体一体化建模：将需要协同排序的所有属性和原始身份标号（如学号、编号、时间戳）合并封装；
2. 比较器层级分支明确：用阶梯式的 if (a.attr != b.attr) return a.attr > b.attr; 依次收敛决策链；
3. 牢记非自反性原则：使用严格的大于或小于运算符，确保排序稳定可靠。

经典同类推荐练习题：

• luogu-P1051 [NOIP 2005 提高组] 谁拿了最多奖学金（结构体模拟与综合评分运算）
• luogu-P1068 [NOIP 2009 普及组] 分数线划定（多关键字排序与分数线下标截断）
• luogu-P1781 宇宙总统（结构体多关键字结合大整数位数与字典序比较）
• luogu-P1104 生日（年、月、日多层日期比较与逆序学号判定）