【NOIP真题】2007 奖学金 luogu-P1093 | 适用于 GESP四级 / CSP-J 练习

四季读书网 2026-10-03 11:13:39 7 0

💡 GESP 考级与信奥算法精选

【NOIP真题】2007 奖学金 luogu-P1093 | 适用于 GESP四级 / CSP-J 练习

✍️ 作者：OneCoder•🏷️ 分类：GESP / 四级 / 排序 / CSP-J

在实际的评奖评优与考务系统中，如何按照多元维度公平、唯一地确定排名次序？洛谷 P1093 [NOIP2007 普及组]《奖学金》提供了一个标准的现实场景：根据三门课程总分、单科语文分以及学号先后来打破平局。这道题是信奥考查**结构体建模（struct）与多关键字自定义排序规则（严格弱序）**的标志性试题。对于 GESP 四级与 CSP-J 入门考生而言，掌握如何设计稳定的比较函数，将现实中的多级仲裁逻辑转化为优雅的计算机排序代码，是迈向复杂数据处理的必备基本功。

P1093 [NOIP2007 普及组] 奖学金

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

🔹 题目描述

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

任务：先根据输入的门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名学生的学号和总分。注意，在前名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：

7 2795 279

这两行数据表示，学号为的同学总分为，学号为的同学总分为。在不同的答卷中，双方总分都是，但学号为的同学语文成绩高一些，所以排在前面。

🔹 输入格式

共行。

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

第到行，每行有个空格隔开的数字，每个数字都在到之间，分别表示一个学生的语文、数学、英语成绩。学生学号按输入顺序编号为（恰好是输入数据的行号减）。

🔹 输出格式

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

🔹 输入输出样例

输入 #1

690 67 8087 66 9178 89 9188 99 7767 89 6478 89 98

输出 #1

6 2654 2643 2582 2441 237

输入 #2

880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98

输出 #2

8 2652 2646 2641 2585 258

🔹 说明/提示

数据规模与约定

对于的数据，保证。

🔹 题目深度剖析

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

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

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

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

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

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

第一主关键字：总分降序
若两个学生的 total 不相等，总分更高者优先排前（即 a.total > b.total）；
第二关键字：语文成绩降序
若总分相同（a.total == b.total），比较单科语文，语文分数高者优先排前（即 a.chinese > b.chinese）；
第三关键字：学号升序
若总分与语文均相同，比较两人的初始学号，学号更小者优先排前（即 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. 学号的正确初始化与维护

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

cpp

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）

本题数据规模：

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

3. 输出前 5 名边界保障

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

cpp

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

🔹 完整参考代码 (C++)

cpp

/** * Problem: luogu P1093 [NOIP2007 普及组] 奖学金 * Algorithm: 结构体与多关键字排序 * GESP Level: 四级 (CSP-J 基础) * Author: OneCoder */#include<iostream>#include<vector>#include<algorithm>usingnamespace std;// 1. 定义学生结构体，集中封装学号、各科成绩与总分structStudent {int id; // 学生学号 (1 ~ n)int chinese; // 语文单科成绩int math; // 数学单科成绩int english; // 英语单科成绩int total; // 三科总分};// 2. 自定义多关键字比较函数// 遵循严格弱序规范 (Strict Weak Ordering)，严禁使用 >= 或 <=boolcmp(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)constint MAXN = 305;Student stu[MAXN];intmain(){int n; cin >> n;// 读入每个学生的各科成绩并计算总分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"; }return0;}

🔹 复杂度深度分析

时间复杂度
：
- 数据读入
  ：单层循环遍历个学生，耗时；
- 多关键字排序
  ：采用 std::sort 对包含个元素的结构体数组排序。单次比较耗时为，整体排序复杂度为；
- 结果输出
  ：固定输出次，耗时；
- 综合时间复杂度
  为。在最坏规模时，次运算，耗时，瞬时完成。
空间复杂度
：
- 全局静态数组大小为；
- 空间复杂度为，远低于题目的限制。