每次将一名同学插入已排好序的队伍末尾,求最少交换次数。
N 名同学学号 0 ~ N−1,各有身高。老师依次点名 M 名同学加入队伍:新同学先站到队伍末尾,然后整个队伍按身高从低到高重新排序(身高相同的顺序任意)。
每次点名后,求最少需要几次"两人交换位置"才能完成排序。
例:队伍学号依次为 10, 17, 3, 25,让 3 号与 10 号交换位置后变为 3, 17, 10, 25——这是一次交换。
排序的最小交换次数置换的循环分解多重集的等价元素去重计数
| 项目 | 说明 |
|---|---|
| 输入 | N;N 个身高;M;M 次点名(每次给一个学号 x) |
| 输出 | M 行,每行是本次点名后的最少交换次数 |
| 数据范围 | 1 ≤ M ≤ N ≤ 2000 |
| 身高范围 | 不超过 2147483647 |
| 保证 | 每次点名的同学此前不在队伍中 |
n − 置换的循环个数样例 1:身高 [170, 165, 168, 160, 175](学号 0 ~ 4),点名顺序 0, 3, 2, 1。
队伍为空 → 加入后是 [170]
已经有序,交换 0 次
输出 0 ✓
队伍当前是 有序的 [170]
新同学站到末尾 → [170, 160]
要让 160 到前面,交换 1 次
交换后队伍变为 [160, 170]
输出 1 ✓
队伍是有序的 [160, 170]
新同学站到末尾 → [160, 170, 168]
交换 168 与 170 → [160, 168, 170],共 1 次
输出 1 ✓
队伍是有序的 [160, 168, 170]
新同学站到末尾 → [160, 168, 170, 165]
165 需要越到 168、170 前面
最少交换 2 次
输出 2 ✓
这是本题最有价值的一段推理。设新同学身高为 x,队伍里有 a 个比 x 矮、b 个和 x 一样高、c 个比 x 高。
队伍当前:[比x矮的 a 个] [等于x的 b 个] [比x高的 c 个] [x]
排序后应当是:[比x矮的 a 个] [等于x的 b+1 个] [比x高的 c 个]
前面 a + b 个位置本来就对得上 → 可以不动
问题集中在末尾的 c + 1 个位置
只有 c + 1 个位置需处理
末尾这 c + 1 个位置里:当前是 [v₁, v₂, …, v_c, x](v 为比 x 高的数,升序)
目标是 [x, v₁, v₂, …, v_c]
对第 i 个 v(i ≥ 2),若 v_i = v_{i−1},
那么它可以"留在原位"(因为它左边也是同样的值)
所以"能不动"的个数 = 相邻相等的对数
可保留 P 个位置
剩余 c + 1 − P 个位置构成一个循环
交换次数 = (c + 1) − (1 + P) = c − P
其中 P = Σ_{不同值 w > x} (cnt(w) − 1)
而 c = Σ_{不同值 w > x} cnt(w)
所以 c − P = Σ 1 = 不同值的种数
✅ 答案 = 比 x 高的不同身高种数
| 样例片段 | 队伍 | 新同学 x | 比 x 高的值 | 不同种数 | 答案 |
|---|---|---|---|---|---|
| 样例1 第2次 | [170] | 160 | {170} | 1 | 1 ✓ |
| 样例1 第3次 | [160,170] | 168 | {170} | 1 | 1 ✓ |
| 样例1 第4次 | [160,168,170] | 165 | {168,170} | 2 | 2 ✓ |
| 样例2 第4次 | [20,20,20] | 10 | {20} | 1 | 1 ✓ |
[20,20,20],新同学身高 10,有 3 个人比他高,但答案是 1 而不是 3——因为只要和其中一个 20 交换一次,另外两个 20 的位置就自动对了(它们本来就是 20,排在哪儿都是 20)。"相同身高的同学可以互相顶替",这就是省下交换次数的原因。维护已入场同学的身高集合,每次数一数"比新同学高的不同值"有几个
inQ[学号] 标记是否已入场;每次询问时遍历所有已入场的同学,把"身高 > 新同学身高"的身高值去重计数。M、N ≤ 2000,双重循环完全够快。每次插入后真的模拟排序,数交换次数
| 方案 | 复杂度 | 正确性风险 |
|---|---|---|
| 去重计数 | O(NM) | 低(有推导保证) |
| 模拟排序 | O(NM log N) | 高(易误用相邻交换) |
第一行输入 N,第二行输入身高,第三行输入 M,随后 M 行输入点名学号。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int h[2005]; bool inQ[2005]; // 该学号是否已在队伍中 int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &h[i]); int M; scanf("%d", &M); while (M--) { int x; scanf("%d", &x); inQ[x] = true; // 学号 x 加入队伍 // 统计"已在队伍中、且身高严格大于 h[x]"的不同身高种数 vector<int> seen; int cnt = 0; for (int y = 0; y < N; y++) { if (!inQ[y] || h[y] <= h[x]) continue; bool found = false; for (int v : seen) if (v == h[y]) { found = true; break; } if (!found) { seen.push_back(h[y]); cnt++; } } printf("%d\n", cnt); } return 0; }
h[y] > h[x](严格大于),因为身高相同的同学之间不用交换。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
inQ[x] = true | 加入队伍 | 每次点名把该学号标记为已入场 |
h[y] <= h[x] → continue | 筛选 | 严格大于才算"更高" |
seen 去重 | 去重计数 | 同一身高只算一次 |
printf("%d\n", cnt) | 输出 | 每次点名输出一行 |
≥ 而不是 >(身高相同不该计入);③ 忘记新同学加入后要立即更新集合再统计。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 0 1 1 2 | 题面样例 1 |
4 | 0 0 0 1 | 题面样例 2(有相同身高) |
1 | 0 | 只有一名同学 |
3 | 0 1 2 | 每次都在末尾加一个更矮的 |
3 | 0 0 0 | 每次加入更高的,队伍保持有序 |
身高数组、入场标记、去重用的临时数组。
✅ 约 400 万次操作,瞬间完成。N、M ≤ 2000 很小,不需要更高级的数据结构。
// 结论:答案 = 队伍中"比新同学高的不同身高种数" // 因为: // 1. 每次排完序,队伍都是有序的 -> 只有末尾一个异类 // 2. 任意两人可交换 -> 最少次数 = n - 循环个数 // 3. 相同身高的人可以互相顶替 -> 可以保留更多"不动的位置" // 推导得:次数 = c - P = 不同身高种数 // 若题目改成"只能交换相邻两人" // 则答案 = 队伍中"比新同学高的人数"(不是种数!) // 这是两种模型的关键区别 // 用 set 加速去重(N 较大时) set<int> s; for (int y = 0; y < N; y++) if (inQ[y] && h[y] > h[x]) s.insert(h[y]); printf("%d\n", (int)s.size());
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 任意交换模型 | 次数 = n − 循环个数 | 任意两两交换类问题 |
| 相同值可顶替 | 能保留更多不动位 | 多重集排序的最小交换次数 |
| 去重计数 | 同一值只算一次 | 本题的关键结论 |