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函数与自定义比较函数实现多维排序，利用双指针处理并列排名，通过映射还原原始顺序，确保逻辑清晰且高效。
五、总结
本解法核心在于结构体的合理设计与多维排序规则的实现，通过副本排序+映射技巧避免数据混乱。处理并列排名时，利用短路逻辑优化比较效率，双指针遍历减少冗余计算。代码简洁且符合竞赛要求，为同类排序问题提供了可复用的模板。需注意：排序函数需严格遵循题目规则顺序，并列处理需确保区间完整性。
原创内容 转载请注明出处
