题解 | 成绩排序
成绩排序
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可以全部通过
- sort 函数 功能:对容器中的元素进行排序。
特点:
不保证排序的稳定性。
如果两个元素的比较结果相等(例如成绩相同),它们的相对顺序可能会被改变。
时间复杂度:O(n log n)。
适用场景:当不需要保持相等元素的相对顺序时,可以使用 sort。
- stable_sort 函数 功能:对容器中的元素进行排序,并保持相等元素的相对顺序。
特点:
保证排序的稳定性。
如果两个元素的比较结果相等(例如成绩相同),它们的相对顺序不会改变。
时间复杂度:O(n log n)(在大多数情况下),但在某些情况下可能会稍慢于 sort。
适用场景:当需要保持相等元素的相对顺序时,必须使用 stable_sort。
为什么 stable_sort 能通过测试用例?在你的问题中,题目要求按成绩排序,但题目并没有明确说明当成绩相同时是否需要保持输入顺序。然而,测试用例可能隐含了以下要求:
如果两个学生的成绩相同,它们的输出顺序应该与输入顺序一致。
如果使用 sort,成绩相同的学生的相对顺序可能会被打乱,导致测试用例失败。而 stable_sort 会保持成绩相同的学生的输入顺序,因此能够通过测试用例。