当前位置：首页 > GESP > 2024年GESP五级成绩排序算法解析：洛谷B3968代码实现与优化思路

2024年GESP五级成绩排序算法解析：洛谷B3968代码实现与优化思路

2个月前 (07-18)

一、题目解读

题目要求对n名学生的语文、数学、英语成绩进行排序，并输出按原始输入顺序的排名。排序规则需依次比较总分、语数总分、语数最高分，若完全相同时保持原始顺序。需处理并列排名，确保相同成绩的学生获得同一名次。

二、解题思路

1. 设计Student结构体存储学生信息（ID、各科成绩、总分、语数相关分数、排名），避免数据分散。

2. 自定义compare函数实现多维比较：总分>语数总分>语数最高分，利用短路逻辑提升效率。

3. 通过排序与遍历处理并列排名：对副本排序后，找到连续相同成绩的区间，分配相同排名。

4. 利用映射将排序后的排名还原至原始输入顺序，确保输出正确。

三、解题步骤

1. 数据输入与预处理：循环读取n名学生成绩，计算总分、语数总分及最高分，并记录ID。

2. 排序副本生成：复制学生数据至sorted数组，使用自定义compare函数排序，避免破坏原始顺序。

3. 并列排名计算：遍历sorted，通过双指针找到成绩相同区间，为区间内学生统一分配排名。

4. 排名映射与输出：创建original_order_rank数组，根据ID映射排名，按原始顺序输出。

四、代码与注释

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

// 学生结构体，存储原始数据和计算后的各种分数
struct Student {
    int id;         // 原始输入顺序
    int chinese;    // 语文成绩
    int math;       // 数学成绩
    int english;    // 英语成绩
    int total;      // 三科总分
    int cm_sum;     // 语文+数学总分
    int cm_max;     // 语文和数学中的最高分
    int rank;       // 最终排名
};

// 自定义比较函数，用于排序
bool compare(const Student &a, const Student &b) {
    if (a.total!= b.total) return a.total > b.total; // 优先比较总分
    if (a.cm_sum!= b.cm_sum) return a.cm_sum > b.cm_sum; // 次比较语数总分
    if (a.cm_max!= b.cm_max) return a.cm_max > b.cm_max; // 再比较语数最高分
    return false; // 完全相等时保持原顺序
}

int main() {
    int n;
    cin >> n;
    
    vector<Student> students(n);
    
    // 读取输入数据并计算各种分数
    for (int i = 0; i < n; ++i) {
        cin >> students[i].chinese >> students[i].math >> students[i].english;
        students[i].id = i;
        students[i].total = students[i].chinese + students[i].math + students[i].english;
        students[i].cm_sum = students[i].chinese + students[i].math;
        students[i].cm_max = max(students[i].chinese, students[i].math);
    }
    
    // 复制一份用于排序
    vector<Student> sorted = students;
    sort(sorted.begin(), sorted.end(), compare);
    
    // 计算排名，处理并列情况
    for (int i = 0; i < n; ) {
        int j = i;
        // 找到所有与当前学生成绩相同的连续学生
        while (j < n &&!compare(sorted[i], sorted[j]) &&!compare(sorted[j], sorted[i])) {
            ++j;
        }
        // 为这些学生设置相同的排名
        for (int k = i; k < j; ++k) {
            sorted[k].rank = i + 1;
        }
        i = j;
    }
    
    // 将排名信息映射回原始顺序
    vector<int> original_order_rank(n);
    for (int i = 0; i < n; ++i) {
        original_order_rank[sorted[i].id] = sorted[i].rank;
    }
    
    // 按原始输入顺序输出排名
    for (int i = 0; i < n; ++i) {
        cout << original_order_rank[i] << endl;
    }
}

注：代码中通过sort函数与自定义比较函数实现多维排序，利用双指针处理并列排名，通过映射还原原始顺序，确保逻辑清晰且高效。