B3968 [GESP202403 五级] 成绩排序

· · 题解

B3968 [GESP202403 五级] 成绩排序 题解

题目链接

题目大意

给定 n 个学生的成绩，将这 n 个学生的成绩按照题目要求排序后按输入顺序输出他们的排名。

题目分析

这是一道非常典型的自定义排序的题目，最关键的点就在于输出排名的时候要按照输入顺序输出，且存在日常生活中的“并列占位”情况。

对于这道题来说，我们需要一个结构体储存所有学生的信息：

struct student {
    int id, c, m, e, total, highest, sum;
    /*id为输入顺序,c,m,e含义如题所述,total记录总分,
    highest记录语文和数学的最高分,sum记录语文和数学的总分*/
} a[maxn];

下面一个问题，如何排序呢？ 库函数能够支持我们自定义排序方法，可以胜任这道题目：

bool cmp(student a, student b) {//排序代码
    if (a.total > b.total) return 1;//比较总分
    else if (a.total < b.total) return 0;
    else {
        if (a.sum > b.sum) return 1;//比较语文数学分数和
        else if (a.sum < b.sum) return 0;
        else {
            if (a.highest > b.highest) return 1;//比较语文数学最高分
            else if (a.highest < b.highest) return 0;
            else return a.id < b.id;
        }
    }
}

然后就是这道题最关键的部分：如何正确地输出呢？我们不妨用一个 ans 数组记录输出的内容。因为这时所有学生的成绩已经是从高往低排序好的，所以我们可以定义一个变量 last 记录上一个学生的信息，如果这个学生部分信息和上一个学生部分信息相同，说明他们是并列的：

bool check(int num1, int num2) {//判断是否并列
    if (a[num1].total == a[num2].total &&
        a[num1].sum == a[num2].sum &&
        a[num1].highest == a[num2].highest) return 1;
    else return 0;
}

这时候我们就要考虑处理并列的问题了。我们可以定义一个 k，代表要额外空出几个位置。每出现一个并列的学生，就将 k 累加 1。需要注意的是，每次用完 k 之后，都要把 k 清零，否则会出错。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
struct student {
    int id, c, m, e, total, highest, sum;
    /*id为输入顺序,c,m,e含义如题所述,total记录总分,
    highest记录语文和数学的最高分,sum记录语文和数学的总分*/
} a[maxn];
int n, p = 1;
//p记录用到了第几个位置
int k;
int ans[maxn], last;
bool cmp(student a, student b) {//排序代码
    if (a.total > b.total) return 1;//比较总分
    else if (a.total < b.total) return 0;
    else {
        if (a.sum > b.sum) return 1;//比较语文数学分数和
        else if (a.sum < b.sum) return 0;
        else {
            if (a.highest > b.highest) return 1;//比较语文数学最高分
            else if (a.highest < b.highest) return 0;
            else return a.id < b.id;
        }
    }
}
bool check(int num1, int num2) {//判断是否并列
    if (a[num1].total == a[num2].total &&
        a[num1].sum == a[num2].sum &&
        a[num1].highest == a[num2].highest) return 1;
    else return 0;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].c >> a[i].m >> a[i].e;
        a[i].id = i;
        a[i].total = a[i].c + a[i].m + a[i].e;
        a[i].highest = max(a[i].c, a[i].m);
        a[i].sum = a[i].c + a[i].m;
    }
    sort(a + 1, a + n + 1, cmp);
    ans[a[1].id] = 1;
    last = 1;
    for (int i = 2; i <= n; i++) {
        if (check(last, i)) {//有并列的学生
            ans[a[i].id] = p;//记录排名
            k++;//是并列的学生,累加k
            last = i;
            continue;
        }
        p += k + 1;//并列结束,新的占位
        k = 0;//记得清空
        ans[a[i].id] = p;//记录排名
        last = i;//更新缓存信息
    }
    for (int i = 1; i <= n; i++ ) {
        cout << ans[i] << endl;
    }
    return 0;
}