题解 | 成绩排序

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

using namespace std;

// 定义学生结构体
struct Student {
    string name;
    int score;
};

// 比较函数，用于升序排序
bool compareAsc(const Student &a, const Student &b) {
    return a.score < b.score;
}

// 比较函数，用于降序排序
bool compareDesc(const Student &a, const Student &b) {
    return a.score > b.score;
}

int main() {
    int n, op;
    cin >> n; // 输入学生人数
    cin >> op; // 输入排序方式

    vector<Student> students(n);

    // 输入学生姓名和成绩
    for (int i = 0; i < n; ++i) {
        cin >> students[i].name >> students[i].score;
    }

    // 根据排序方式选择比较函数
    if (op == 1) {
        stable_sort(students.begin(), students.end(), compareAsc); // 升序排序
    } else {
        stable_sort(students.begin(), students.end(), compareDesc); // 降序排序
    }

    // 输出排序后的结果
    for (const auto &student : students) {
        cout << student.name << " " << student.score << endl;
    }

    return 0;
}

笔记：sort只能通过6个测试用例，而stable_sort可以全部通过

1. sort 函数 功能：对容器中的元素进行排序。

特点：

不保证排序的稳定性。

如果两个元素的比较结果相等（例如成绩相同），它们的相对顺序可能会被改变。

时间复杂度：O(n log n)。

适用场景：当不需要保持相等元素的相对顺序时，可以使用 sort。

1. stable_sort 函数 功能：对容器中的元素进行排序，并保持相等元素的相对顺序。

特点：

保证排序的稳定性。

如果两个元素的比较结果相等（例如成绩相同），它们的相对顺序不会改变。

时间复杂度：O(n log n)（在大多数情况下），但在某些情况下可能会稍慢于 sort。

适用场景：当需要保持相等元素的相对顺序时，必须使用 stable_sort。

为什么 stable_sort 能通过测试用例？在你的问题中，题目要求按成绩排序，但题目并没有明确说明当成绩相同时是否需要保持输入顺序。然而，测试用例可能隐含了以下要求：

如果两个学生的成绩相同，它们的输出顺序应该与输入顺序一致。

如果使用 sort，成绩相同的学生的相对顺序可能会被打乱，导致测试用例失败。而 stable_sort 会保持成绩相同的学生的输入顺序，因此能够通过测试用例。