牛客4854题：学生信息排序算法实现与优化

一、题目解读

牛客4854题要求对n个学生的姓名和成绩进行排序，操作op=1时按成绩升序，op=2时按成绩降序，若成绩相同则按原始输入顺序排序。题目核心在于处理双重排序条件：成绩优先级高于输入顺序，需设计合理的排序逻辑。

二、解题思路

1. 使用C++ STL的sort函数简化排序流程，关键在于自定义比较函数。

2. 定义Student结构体存储姓名、成绩及输入顺序（order字段），确保成绩相同时可依据order排序。

3. 根据op选择升序（cmp_asc）或降序（cmp_desc）比较函数，二者均优先比较成绩，成绩相同则比较order。

三、解题步骤

1. 输入学生数量n与排序操作op。

2. 创建Student数组并读取姓名、成绩，同时记录当前输入顺序（i）。

3. 根据op选择排序方式：

    op=1调用sort(students, cmp_asc)升序排序；

    op=2调用sort(students, cmp_desc)降序排序。

4. 遍历排序后的students输出姓名与成绩。

四、代码及注释

C++

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

struct Student {
    string name;
    int score;
    int order;  // 记录输入顺序（关键！解决成绩相同时的排序依据）
};

// 升序比较函数
bool cmp_asc(const Student &a, const Student &b) {
    if(a.score!= b.score) return a.score < b.score;  // 优先按成绩升序
    return a.order < b.order;  // 成绩相同按输入顺序
}

// 降序比较函数
bool cmp_desc(const Student &a, const Student &b) {
    if(a.score!= b.score) return a.score > b.score;  // 优先按成绩降序
    return a.order < b.order;  // 成绩相同按输入顺序
}

int main() {
    int n, op;
    cin >> n >> op;  // 输入学生数与排序操作

    vector<Student> students(n);
    for(int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].score;
        students[i].order = i;  // 记录当前学生的输入顺序
    }
    
    // 根据op选择排序方式
    if(op == 1) {
        sort(students.begin(), students.end(), cmp_asc);
    } else {
        sort(students.begin(), students.end(), cmp_desc);
    }
    
    // 输出排序结果
    for(const auto &s : students) {
        cout << s.name << " " << s.score << endl;
    }
    
    return 0;
}

五、总结

1. 自定义比较函数是sort函数处理复杂排序的核心，需明确优先级逻辑（成绩 > 输入顺序）。

2. 记录输入顺序的“order”字段巧妙解决成绩相同时的二重排序问题，避免额外数据结构。

3. 利用sort函数提升效率，避免手动编写冒泡/选择排序的复杂性与低效性。

4. 该解法兼顾代码简洁性与算法正确性，适合实际编程场景。

来源：牛客4854题：学生信息排序算法实现与优化