按四级规则排序后,按输入顺序输出每人的排名(并列同名次、后续名次跳过)。
n 名同学各有语文、数学、英语三科成绩。按以下规则从高到低排序:
输出每位同学的排名(按输入顺序输出各自的排名)。若 x 人并列,则他们名次相同,并占用后面的 x − 1 个名次。
例:3 人并列第 1,则下一名同学是第 4 名。
多关键字排序并列名次排名计算稳定输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n 行每行三个非负整数 c、m、e |
| 输出 | n 行,按输入顺序输出每人的排名 |
| 排序键 | 总分 → 语数总分 → 语数最高分 |
| 并列 | 四项都相同即并列,名次相同且跳过后续名次 |
先算出每个人的三个排序键。
| 输入序号 | 语 c | 数 m | 英 e | 总分 | 语数和 | 语数最高 |
|---|---|---|---|---|---|---|
| 1 | 140 | 140 | 150 | 430 | 280 | 140 |
| 2 | 140 | 149 | 140 | 429 | 289 | 149 |
| 3 | 148 | 141 | 140 | 429 | 289 | 148 |
| 4 | 141 | 148 | 140 | 429 | 289 | 148 |
| 5 | 145 | 145 | 139 | 429 | 290 | 145 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 |
1 号总分 430,最高 → 排第 1
2、3、4、5 号总分都是 429 → 进入第 2 级
6 号总分 0,最低 → 排最后
1 号第 1,6 号最后
5 号语数和 290(最高)→ 排第 2
2、3、4 号语数和都是 289 → 进入第 3 级
5 号第 2
2 号最高分 149 → 排第 3
3 号、4 号都是 148 → 并列
两人并列,占用第 4、5 两个名次位置
所以他们都记作第 4 名
2 号第 3,3、4 号并列第 4
6 号独自一人,总分 0
它前面的并列组占了 2 个名次(第 4、5)
所以它是第 6 名
6 号第 6
| 输入序号 | 名次 | 说明 |
|---|---|---|
| 1 | 1 | 总分最高 |
| 2 | 3 | 语数最高分 149,排第 3 |
| 3 | 4 | 与 4 号并列第 4 |
| 4 | 4 | 与 3 号并列第 4 |
| 5 | 2 | 语数总分 290,排第 2 |
| 6 | 6 | 总分 0,排第 6(跳过了第 5 名) |
输出 1、3、4、4、2、6 ✓
用"组内名次 = 组首位置"这个规则实现最简洁。
排序后的顺序(按规则):1 号、5 号、2 号、3 号、4 号、6 号
遍历数组的下标 k = 0, 1, 2, 3, 4, 5
若 k == 0 或 第 k 人与第 k−1 人不并列,则把该组的名次记为 k + 1
否则沿用当前组的名次
一轮扫描即可
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 依次输出。直接输出排序后的名次序列是错的。按四级键排序,再从前往后扫一遍,组首给名次
if (k == 0 || !tie(next, prev)) rnk = k + 1;——只有"不是并列"时才更新名次为当前位置 + 1,并列时沿用上一人的名次。双重循环统计严格优于我的人数,名次 = 该数量 + 1
| 方案 | 复杂度 | 适用规模 |
|---|---|---|
| 排序 + 扫描 | O(n log n) | 任意规模 |
| 两两比较 | O(n²) | 仅小数据 |
第一行输入 n,随后 n 行每行三科成绩,程序会按四级规则排序并给出排名。
点按钮开始 →
#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 | 记录名次 | 按原始编号存储,便于最后按输入顺序输出 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 1 3 4 4 2 6 | 题面样例 |
1 | 1 | 只有一人 |
2 | 1 1 | 两人完全相同,并列第 1 |
2 | 1 1 | 总分 290、语数和 190、语数最高 100 三项全同 → 并列第 1 |
3 | 1 2 2 | 后两人并列第 2,没有第 3 名 |
需要存 n 个同学的信息和一份名次表。
✅ 排序是主要开销,任意 n 规模都能轻松完成。
// 并列排名的标准算法("组首位置即名次") 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 | 所有自定义比较函数 |
| 按原序输出 | 用编号映射回名次 | 所有"打乱后按原序输出"的题 |
rnk = k + 1 改成 rnk++——注意两种排名的规则完全不同,读题时必须看清"是否跳过名次"。)