夜雨聆风学习资料网

ARTICLE · 1117831

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

发布时间：2026-10-03 11:12:47 最近访问：2026-10-03 11:12:47
【NOIP真题】2007 奖学金 luogu-P1093 | 适用于 GESP四级 / CSP-J 练习
         💡 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) 必须按由主到次的规则依序判定：

  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. 学号的正确初始化与维护

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

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 对包含  个元素的结构体数组排序。单次比较耗时为 ，整体排序复杂度为 ；
    • 结果输出
      ：固定输出  次，耗时 ；
    • 综合时间复杂度
      为 。在最坏规模  时， 次运算，耗时 ，瞬时完成。
  • 空间复杂度
    ： 
    • 全局静态数组大小为 ；
    • 空间复杂度为 ，远低于题目的  限制。

🔹 总结与同类考点拓展

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

  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 生日（年、月、日多层日期比较与逆序学号判定）
📚 往期关联真题与系统化备考：

           本站已收录超 900+ 篇计算机与算法专题。由于微信公众号不支持外部链接直接跳转，建议点击左下角「阅读原文」直达个人网站，即可使用全局检索（Ctrl+K）、在线复制代码与浏览完整知识库！         

长按关注「OneCoder」公众号

相关学习资料