GESP 题解库 / 5 级题解 / [GESP202403 五级] 成绩排序 · 第 14 / 23 题
GESP202403 五级 · B3968 · 简单

成绩排序

按四级规则排序后,按输入顺序输出每人的排名(并列同名次、后续名次跳过)。

📊
n ≤ ?
同学人数
🔢
int
数值类型
⚡
O(n log n)
时间复杂度
🎯
多关键字排序 + 并列名次
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

n 名同学各有语文、数学、英语三科成绩。按以下规则从高到低排序:

  1. 比较总分,高者靠前
  2. 总分相同则比较语文 + 数学,高者靠前
  3. 仍相同则比较语文、数学中的最高分,高者靠前
  4. 仍相同则并列

输出每位同学的排名(按输入顺序输出各自的排名)。若 x 人并列,则他们名次相同,并占用后面的 x − 1 个名次。

例:3 人并列第 1,则下一名同学是第 4 名。

💡
人话翻译:这题有两个要点:① 四级排序键(总分 → 语数总分 → 语数最高分);② 名次的计算方式——排列名次不是"该人在有序列表中的位置",而是"严格优于我的人数 + 1"。这样并列的人会得到相同名次,且后续名次自动跳过。

🔍 关键词提取

多关键字排序并列名次排名计算稳定输出

已知条件

项目说明
输入第一行 n;随后 n 行每行三个非负整数 c、m、e
输出n 行,按输入顺序输出每人的排名
排序键总分 → 语数总分 → 语数最高分
并列四项都相同即并列,名次相同且跳过后续名次

需要解决的问题

02
思维导图
整理解题思路的全貌
🏅 四级键排序 + 跳过式名次
📥 读入
n 名同学
三科成绩 c、m、e
记住输入顺序
需要按顺序输出排名
⚖️ 四级键
总分 = c+m+e
语数和 = c+m
语数最高 = max(c,m)
依次比较
🏆 名次计算
排序后从左到右扫
第一个不同组给 名次 = 下标+1
并列组内名次相同
下一组自动跳到实际位置
⚠️ 易错点
按排名输出而非输入顺序
并列名次没跳过
比较键顺序写错
用"下标+1"当名次(并列时不正确)
03
样例手算推导
样例 6 人的排序与名次

🧮 样例:6 名同学

先算出每个人的三个排序键。

输入序号语 c数 m英 e总分语数和语数最高
1140140150430280140
2140149140429289149
3148141140429289148
4141148140429289148
5145145139429290145
6000000
1
第 1 级:比总分

1 号总分 430,最高 → 排第 1

2、3、4、5 号总分都是 429 → 进入第 2 级

6 号总分 0,最低 → 排最后

1 号第 1,6 号最后

2
第 2 级:比语数总分

5 号语数和 290(最高)→ 排第 2

2、3、4 号语数和都是 289 → 进入第 3 级

5 号第 2

3
第 3 级:比语数最高分

2 号最高分 149 → 排第 3

3 号、4 号都是 148 → 并列

两人并列,占用第 4、5 两个名次位置

所以他们都记作第 4 名

2 号第 3,3、4 号并列第 4

4
第 4 级:完全并列

6 号独自一人,总分 0

它前面的并列组占了 2 个名次(第 4、5)

所以它是第 6 名

6 号第 6

📊 按输入顺序输出的排名

输入序号名次说明
11总分最高
23语数最高分 149,排第 3
34与 4 号并列第 4
44与 3 号并列第 4
52语数总分 290,排第 2
66总分 0,排第 6(跳过了第 5 名)

输出 1、3、4、4、2、6 ✓

🔑
关键点:名次不是"排序后的位置"!如果直接输出"排序后的下标 + 1",3 号会得到 4、4 号会得到 5——那就错了。正确做法是"并列的人用同一个名次,且名次等于该组第一个人的位置",所以 3、4 号都是第 4 名,下一组的 6 号直接跳到第 6 名。

🧮 名次的标准算法

用"组内名次 = 组首位置"这个规则实现最简洁。

1
排序后从左到右扫描

排序后的顺序(按规则):1 号、5 号、2 号、3 号、4 号、6 号

遍历数组的下标 k = 0, 1, 2, 3, 4, 5

若 k == 0 或 第 k 人与第 k−1 人不并列,则把该组的名次记为 k + 1

否则沿用当前组的名次

一轮扫描即可

2
具体过程

k = 0:新组 → rank = 1(1 号得第 1)

k = 1:与 1 号不并列 → rank = 2(5 号得第 2)

k = 2:不并列 → rank = 3(2 号得第 3)

k = 3:不并列 → rank = 4(3 号得第 4)

k = 4:与 3 号并列 → 沿用 rank = 4(4 号得第 4)

k = 5:不并列 → rank = 6(6 号得第 6)

✅ 名次正确

// 排序后计算名次(组首位置 = 名次)
for (int k = 0; k < n; k++) {
    if (k == 0 || !tie(v[k], v[k-1])) rnk = k + 1;
    rankOf[v[k].id] = rnk;
}
// rankOf 按原始编号记录名次
⚠️
注意最后的输出:题目要求按输入顺序输出每人的排名,所以要用一个 rankOf[编号] 数组把名次映射回原始编号,最后从 1 到 n 依次输出。直接输出排序后的名次序列是错的。
04
解法对比
结构体排序 + 名次扫描 vs 两两比较

⚔️ 解法对比

🟢 排序 + 一次扫描定名次(推荐) 推荐

按四级键排序,再从前往后扫一遍,组首给名次

  • 时间 O(n log n)
  • 一次排序 + 一次扫描
  • 并列处理天然正确
  • 代码 30 行
💡
核心:if (k == 0 || !tie(next, prev)) rnk = k + 1;——只有"不是并列"时才更新名次为当前位置 + 1,并列时沿用上一人的名次。

🟠 对每个人数"比我强的有几个"

双重循环统计严格优于我的人数,名次 = 该数量 + 1

  • 时间 O(n²)
  • n 大时会超时
  • 逻辑更直白(贴合"跳过式名次"定义)
  • 但效率差
⚠️
两种都对:"名次 = 严格优于我的人数 + 1"正是并列跳名的数学表达。小数据下这种写法更容易理解,但排序法是大数据下的标准做法。

📈 性能对比

方案复杂度适用规模
排序 + 扫描O(n log n)任意规模
两两比较O(n²)仅小数据
05
算法流程图
四级键排序后扫描定名次
开始读入 n 和每人三科成绩;记下原始编号按 (总分降序, 语数和降序, 语数最高降序) 排序从前往后扫描,k = 0 起k == 0 或 与上一位不并列吗?是 ✓当前名次 = k + 1否 ✗沿用上一人的名次把当前名次记录到 rankOf[该同学的原始编号]按原始编号 1 到 n 依次输出名次结束k 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏅 成绩排名计算器

第一行输入 n,随后 n 行每行三科成绩,程序会按四级规则排序并给出排名。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

struct Stu {
    int id;          // 原始编号(1 起)
    int c, m, e;     // 语、数、英
    int tot() const { return c + m + e; }        // 总分
    int cm()  const { return c + m; }            // 语数和
    int cmx() const { return max(c, m); }        // 语数最高分
};

// 多关键字比较:返回 a 是否应排在 b 前面
bool better(const Stu &a, const Stu &b) {
    if (a.tot() != b.tot()) return a.tot() > b.tot();
    if (a.cm()  != b.cm())  return a.cm()  > b.cm();
    if (a.cmx() != b.cmx()) return a.cmx() > b.cmx();
    return false;                 // 完全并列:谁也不比谁靠前
}

// 判断两人是否并列
bool tied(const Stu &a, const Stu &b) {
    return a.tot() == b.tot() && a.cm() == b.cm() && a.cmx() == b.cmx();
}

int main() {
    int n;
    scanf("%d", &n);

    vector<Stu> v(n);
    for (int i = 0; i < n; i++) {
        v[i].id = i + 1;
        scanf("%d %d %d", &v[i].c, &v[i].m, &v[i].e);
    }

    sort(v.begin(), v.end(), better);

    // 扫描定名次:组首位置即名次
    vector<int> rankOf(n + 1);
    int rnk = 0;
    for (int k = 0; k < n; k++) {
        if (k == 0 || !tied(v[k], v[k - 1])) rnk = k + 1;
        rankOf[v[k].id] = rnk;
    }

    // 按输入顺序输出
    for (int i = 1; i <= n; i++) printf("%d\n", rankOf[i]);
    return 0;
}
🔑
为什么比较函数在"完全并列"时返回 false?因为排序要求"严格弱序":better(a,b) 为真表示 a 应排在 b 前。两人完全并列时,谁也不该排在谁前面,所以返回 false。如果这里返回 true,会破坏排序的一致性,可能导致未定义行为。

📖 关键几行怎么看

代码作用为什么这样写
a.tot() > b.tot()降序比较高者靠前,用 >
return false并列谁也不比谁靠前
if (k == 0 || !tied(v[k], v[k-1])) rnk = k + 1;定名次组首位置即名次
rankOf[v[k].id] = rnk记录名次按原始编号存储,便于最后按输入顺序输出
⚠️
三个坑:① 把"排序后的下标 + 1"当名次(并列时错误);② 按排序后的顺序输出(应该按输入顺序);③ 比较函数在并列时返回 true,破坏严格弱序。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6
140 140 150 / 140 149 140 / 148 141 140 / 141 148 140 / 145 145 139 / 0 0 0
1
3
4
4
2
6
题面样例
1
100 100 100
1只有一人
2
100 100 100 / 100 100 100
1
1
两人完全相同,并列第 1
2
90 100 100 / 100 90 100
1
1
总分 290、语数和 190、语数最高 100 三项全同 → 并列第 1
3
150 150 150 / 100 100 100 / 100 100 100
1
2
2
后两人并列第 2,没有第 3 名
✅
自查清单:① 三个排序键顺序对吗?② 并列时名次取组首位置吗?③ 按输入顺序输出吗?

🚨 易错点清单

⚠️
名次算成"下标 + 1":并列的人应取相同名次(组首位置),而不是各自的下标 + 1。
⚠️
输出顺序错:必须按输入顺序输出每人的名次,不能用排序后的顺序。
⚠️
比较键顺序写错:必须是 总分 → 语数和 → 语数最高分。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 规模
本题不大
运算量
排序为主

时间怎么算的?

空间都用在哪?

需要存 n 个同学的信息和一份名次表。

✅ 排序是主要开销,任意 n 规模都能轻松完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 并列排名的标准算法("组首位置即名次")
int rnk = 0;
for (int k = 0; k < n; k++) {
    if (k == 0 || !tied(v[k], v[k-1])) rnk = k + 1;
    rankOf[v[k].id] = rnk;
}

// 另一种等价理解:名次 = 严格优于我的人数 + 1
int betterCount = 0;
for (int j = 0; j < n; j++)
    if (j != i && isBetter(v[j], v[i])) betterCount++;
rankOf[i] = betterCount + 1;

// 多关键字比较用 tuple 简化(C++11)
auto key = [](const Stu &s) {
    return make_tuple(-s.tot(), -s.cm(), -s.cmx());   // 取负实现降序
};
sort(v.begin(), v.end(), [&](const Stu &a, const Stu &b){
    return key(a) < key(b);
});

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
并列名次组首位置即名次排行榜、竞赛名次、成绩排名
严格弱序并列时返回 false所有自定义比较函数
按原序输出用编号映射回名次所有"打乱后按原序输出"的题
🌟
思考题:如果题目改成"不跳过名次"(即并列的人名次相同,但下一人只 +1,如两人并列第 1 则下一人是第 2 名),代码要怎么改?(提示:那种叫"竞争排名",只需把 rnk = k + 1 改成 rnk++——注意两种排名的规则完全不同,读题时必须看清"是否跳过名次"。)