P4625 总分排序（入门）

解题思路

n 名学生每人有学号、语文、数学成绩，要把他们按总分（语文+数学）从高到低排序。这道题比“奖学金”简单，因为题目保证每个学生的总分都不相同，所以只要按总分降序排序即可，不用处理并列的情况。读入时算好总分存入结构体，然后 sort() 按总分从大到小排序，最后依次输出学号和总分，中间用空格隔开。

举一个具体的例子：学生 2 语文 90、数学 98，总分 188 最高，排在第一位；学生 1 总分 178 排第二；后面依次是学生 4 的 156、学生 5 的 150、学生 3 的 140。因为总分互不相同，所以排序结果是唯一的，不会出现谁先谁后的争论，比较函数里只需要比一个总分就行。

读入时每一行是学号、语文、数学三个整数，先读学号，再读两科成绩，马上算出总分，不用把语文数学单独保存，能省就省。自定义比较函数返回 a.sum > b.sum，表示总分大的排前面。学号是输入里的第一个数，读入顺序不能搞错，排序后学号会跟着总分一起移动，所以不会弄混。

参考代码

// 用途：按语文和数学总分从高到低排序，输出学生的学号和总分。
#include <iostream>
#include <algorithm>
using namespace std;

struct Student {
    int id;             // 学生的学号
    int sum;            // 学生的语文数学总分
};

// 排序规则：总分高的排前面
bool cmp(const Student& a, const Student& b) {
    return a.sum > b.sum;
}

int main() {
    int n;                              // 学生人数
    cin >> n;                           // 读入学生人数
    Student a[105];                     // 保存学生信息

    for (int i = 0; i < n; i++) {       // 依次读入每名学生
        int chinese, math;              // 当前学生的语文、数学成绩
        cin >> a[i].id >> chinese >> math; // 读入学号和两科成绩
        a[i].sum = chinese + math;      // 计算总分
    }
    sort(a, a + n, cmp);                // 按总分从高到低排序

    for (int i = 0; i < n; i++) {       // 输出排序结果
        cout << a[i].id << ' ' << a[i].sum << '\n'; // 输出学号和总分
    }
    return 0;                           // 程序结束
}

复杂度分析

sort() 时间 O(n log n)，n 最大 100，运行极快。程序用结构体数组保存学生，空间 O(n)。数组下标从 0 开始，读入 n 个人后 sort(a, a+n) 正好覆盖全部元素。比较函数只用总分一个条件，因为题目保证总分互不相同，这样写既简单又不会出错，这也是与“奖学金”一题最大的区别。n 最大 100，数组开 105 足够，多出的几个元素是保险余量，防止边界写错时越界。