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

知识点：多关键字排序、排名、并列处理。

解题思路

为每人构造总分、语数和、语数较高分三个关键字，降序排序。只有关键字三元组变化时，名次变为当前位置+1，再按原编号输出。

为什么正确

相同评价关键字属于同一并列组，组首位置是该组正确名次，保留组内名次并映射回原序即可。

易错点

并列后的名次需跳号；原编号只是恢复输出位置，不参与决定是否并列。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<tuple<int,int,int,int>>a;
    for(int i=0;i<n;i++) {
        int c,m,e;
        cin>>c>>m>>e;
        a.emplace_back(c+m+e,c+m,max(c,m),i);
    }
    sort(a.rbegin(),a.rend());
    vector<int>ans(n);
    int rank=1;
    for(int i=0;i<n;i++) {
        auto [s,t,h,j]=a[i];
        if(i) {
            auto [ps,pt,ph,pj]=a[i-1];
            if(tie(s,t,h)!=tie(ps,pt,ph))rank=i+1;
        }
        ans[j]=rank;
    }
    for(int x:ans)cout<<x<<"\n";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。