12983.成绩排序

markdown
复制
1# 成绩排序 题解
2
3## 题目分析
4
5我们有 \(N\) 名同学，每名同学有语文、数学、英语三科成绩。排序规则不是简单的比总分，而是一套**多关键字排序**规则：
6
71. 首先比较**总分**（语文 + 数学 + 英语），总分高的靠前；
82. 总分相同，比较**语文 + 数学**的总分，高的靠前；
93. 如果还相同，比较**语文和数学中的最高分**（即 \(\max(\text{语文}, \text{数学})\)），高的靠前；
104. 如果三个关键字都相同，则两名同学**并列**。
11
12排名规则要求：如果有 \(x\) 人并列第 \(p\) 名，则他们都输出 \(p\)，并且接下来的第 \(x+1\) 名同学的名次是 \(p+x\)（空出中间名次）。  
13最后需要按照**输入顺序**输出每位同学的排名，而不是按名次输出同学的序号。
14
15## 解题思路
16
17这道题可以拆成两个部分：
18
19### 1. 多关键字排序
20
21我们需要为每位同学计算三个比较用的**关键值**：
22
23- `total` = 语文 + 数学 + 英语（总分）
24- `sum_cm` = 语文 + 数学（语数总分）
25- `max_cm` = \(\max(\text{语文}, \text{数学})\)（语数最高分）
26
27排序时，按照 `total` 降序，`total` 相同按 `sum_cm` 降序，还相同按 `max_cm` 降序。  
28为了方便输出时找回原始顺序，我们需要在排序前记录每位同学的**原始编号**（输入时的下标）。
29
30### 2. 并列排名的分配
31
32排序完成后，我们从前往后遍历排序结果：
33
34- 维护一个 `last` 三元组，记录上一位同学的前三个关键值；
35- 如果当前同学的关键值与 `last` 完全相同，则他与前一人**并列**，排名相同；
36- 否则，他的排名就是当前的位置序号（从 1 开始），即 `i + 1`。
37
38将计算出的排名保存到 `rank[原始编号]` 中，最后按编号从小到大输出即可。
39
40## 算法说明
41
42我们以 C++ 为实现语言，使用 `std::tuple` 来存储排序所需的四个信息：
43

tuple<总分, 语数总分, 语数最高分, 原始编号>

- `tuple` 默认按照第一关键字 → 第二关键字 → 第三关键字……进行比较，非常适用于多关键字排序。
- 由于题目要求**从高到低排序**，我们可以传入 `greater<...>` 实现降序。

排序结束后，遍历数组，根据前三个关键值判断是否与前一同学并列，更新当前排名，并记录到 `rank` 数组中。

## 参考代码与详细解释

```cpp
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;

const int MAX_N = 10005;
tuple<int, int, int, int> students[MAX_N];

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int c, m, e;
        cin >> c >> m >> e;
        // 构造三元组：总分，语数总分，语数最高分，原始编号
        students[i] = make_tuple(c + m + e, c + m, max(c, m), i);
    }

    // 降序排序
    sort(students, students + N, greater<tuple<int, int, int, int>>());

    int rank[N];               // 存储每名同学的排名（VLA，竞赛中常用）
    int curr_rank;             // 当前名次
    // 前三个关键值初始化为不可能相同的值
    tuple<int, int, int> last_student = make_tuple(-1, -1, -1);

    for (int i = 0; i < N; ++i) {
        // 提取当前同学的前三个关键值
        tuple<int, int, int> now = make_tuple(get<0>(students[i]),
                                              get<1>(students[i]),
                                              get<2>(students[i]));
        if (now != last_student) {
            // 与上一个人不同，更新排名为 i+1
            last_student = now;
            curr_rank = i + 1;
        }
        // 否则排名与上一个人相同，curr_rank 保持不变
        rank[get<3>(students[i])] = curr_rank;  // 按原始编号记录排名
    }

    // 按输入顺序输出排名
    for (int i = 0; i < N; ++i) {
        cout << rank[i] << "\n";
    }
    return 0;
}

代码浅析

1. 数据存储
   students 数组的每个元素是一个四元组，前三个用于比较，第四个是原始编号。make_tuple 快速构造元组。

2. 排序
   sort(students, students + N, greater<...>()) 实现了降序排列。
   greater 会按照元组的顺序依次比较，完全符合题目要求。

3. 排名分配

   • last_student 初始为 (-1,-1,-1)，所有成绩都是非负整数，因此第一次比较必然触发更新。
   • 遍历时，若当前关键值与 last_student 不同，则当前实际排名就是 i+1（因为数组下标从 0 开始）；
     若相同，保持 curr_rank 不变，实现了并列且空出后续名次的效果。
   • 通过 get<3>(students[i]) 取得原始编号，将排名写入 rank 对应位置。

4. 输出
   按原始输入顺序输出 rank 数组即可。

🔧 提示：代码中使用了 int rank[N];，这是变长数组（VLA），在 C++ 标准中并不支持，但多数竞赛编译器（如 GCC）允许使用。如果希望编写更规范的代码，可以用 vector<int> rank(N); 替代。

复杂度分析

• 时间复杂度：排序 (O(N \log N))，排名分配 (O(N))，总体 (O(N \log N))，在 (N \leq 10^4) 时完全可行。
• 空间复杂度：存储学生信息的数组和 rank 数组均与 (N) 成正比，复杂度 (O(N))。

总结

本题是一道典型的多关键字排序 + 并列排名问题。解题的关键在于：

• 正确构造排序所需的组合关键值；
• 利用 tuple 或自定义结构体简化排序过程；
• 理解并列名次的“空名次”规则，通过顺序遍历和比较前一名次的关键值来实现。

掌握这种处理模式，可以轻松应对大部分排序与排名相结合的题目。