洛谷-P1093 [NOIP 2007 普及组] 奖学金 题解

题目链接：https://www.luogu.com.cn/problem/P1093

题解：奖学金（NOIP2007 普及组 T1）

题目大意

有 n 名学生（5 <= n <= 300），每人有语文、数学、英语三科成绩。

定义每个学生的总分为三科成绩之和。

现需按以下规则对所有学生排序，并输出前 5 名的学号和总分：

1. 首先按总分从高到低排序；
2. 若总分相同，按语文成绩从高到低排序；
3. 若总分和语文成绩都相同，按学号从小到大排序（即学号小的排在前面）。

注意：学号从 1 开始，对应输入的第 i 行（i = 1 到 n）。

解题思路

本题是一道典型的多关键字排序问题，关键在于正确实现比较规则。

我们可以为每个学生记录：

• 三科成绩（至少保留语文成绩）；
• 总分；
• 学号。

然后使用自定义比较函数对所有学生进行排序。

排序规则（优先级从高到低）

该规则可通过 std::sort 的 lambda 比较器轻松实现。

代码实现要点

1. 结构体设计定义 Student 结构体，存储：sum：总分；vec[0]：语文成绩（只需第一科）；num：学号（从 1 开始）。
2. 输入处理循环读入 n 行，每行三科成绩，计算总分，并构造 Student 对象存入 vector。
3. 自定义排序使用 lambda 表达式实现上述三级排序规则。
4. 输出前 5 名直接输出排序后前 5 个学生的 学号 和 总分。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
    int sum;      // 总分
    int chinese;  // 语文成绩
    int id;       // 学号

    Student(int s, int c, int i) : sum(s), chinese(c), id(i) {}
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Student> students;
    for (int i = 1; i <= n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        students.emplace_back(a + b + c, a, i); // a 是语文
    }

    // 自定义排序：总分↓ → 语文↓ → 学号↑
    sort(students.begin(), students.end(), [](const Student& x, const Student& y) {
        if (x.sum != y.sum)
            return x.sum > y.sum;
        if (x.chinese != y.chinese)
            return x.chinese > y.chinese;
        return x.id < y.id;
    });

    // 输出前5名
    for (int i = 0; i < 5; ++i) {
        cout << students[i].id << ' ' << students[i].sum << '\n';
    }

    return 0;
}

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序；
• 空间复杂度：O(n)，存储学生信息；
• 对于 n <= 300，效率非常高。