题解 | 成绩排序

成绩排序

https://www.nowcoder.com/practice/8e400fd9905747e4acc2aeed7240978b

#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 会保持成绩相同的学生的输入顺序,因此能够通过测试用例。

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 13:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务