GESP 题解库 / 5 级题解 / [GESP样题 五级] 小杨的队列 · 第 19 / 23 题
GESP样题 五级 · B3951 · 简单

小杨的队列

每次将一名同学插入已排好序的队伍末尾,求最少交换次数。

📊
M ≤ N ≤ 2000
数据规模
🔢
int / long long
身高范围
⚡
O(NM)
时间复杂度
🎯
统计"更大的不同身高数"
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

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
保证每次点名的同学此前不在队伍中

需要解决的问题

02
思维导图
整理解题思路的全貌
🔁 交换次数 = n − 循环数
🧩 基础模型
任意两人可交换
最少交换次数 = n − 循环个数
循环分解来自"位置映射"
相同值可自由匹配
📐 队伍状态
每次排完序后队伍有序
新同学只加在末尾
所以只有"末尾一个异类"
结构非常规整
🔍 切割分析
设 a 个比 x 小的数
b 个等于 x 的数
c 个比 x 大的数
异类只出现在末尾 (c+1) 个位置里
✅ 结论
答案是"比 x 高的不同身高种数"
不是"比 x 高的人数"
相同身高可省交换
用去重计数即可
03
样例手算推导
从样例出发的完整推导

🧮 先看清"队伍始终有序"这件事

样例 1:身高 [170, 165, 168, 160, 175](学号 0 ~ 4),点名顺序 0, 3, 2, 1。

1
第 1 次点名:学号 0(身高 170)

队伍为空 → 加入后是 [170]

已经有序,交换 0 次

输出 0 ✓

2
第 2 次点名:学号 3(身高 160)

队伍当前是 有序的 [170]

新同学站到末尾 → [170, 160]

要让 160 到前面,交换 1 次

交换后队伍变为 [160, 170]

输出 1 ✓

3
第 3 次点名:学号 2(身高 168)

队伍是有序的 [160, 170]

新同学站到末尾 → [160, 170, 168]

交换 168 与 170 → [160, 168, 170],共 1 次

输出 1 ✓

4
第 4 次点名:学号 1(身高 165)

队伍是有序的 [160, 168, 170]

新同学站到末尾 → [160, 168, 170, 165]

165 需要越到 168、170 前面

最少交换 2 次

输出 2 ✓

🔑
核心前提:每次排完序,队伍就变成有序的。所以下一次"插入末尾"时,队伍里只有末尾那一个新同学是"异类"——其余部分已经有序。这让我们能把问题简化成"一个元素插到有序序列的末尾"。

🧮 为什么答案是"不同身高的种数"

这是本题最有价值的一段推理。设新同学身高为 x,队伍里有 a 个比 x 矮、b 个和 x 一样高、c 个比 x 高。

1
找出"位置对不上"的范围

队伍当前:[比x矮的 a 个] [等于x的 b 个] [比x高的 c 个] [x]

排序后应当是:[比x矮的 a 个] [等于x的 b+1 个] [比x高的 c 个]

前面 a + b 个位置本来就对得上 → 可以不动

问题集中在末尾的 c + 1 个位置

只有 c + 1 个位置需处理

2
数一数"能不动"的位置

末尾这 c + 1 个位置里:当前是 [v₁, v₂, …, v_c, x](v 为比 x 高的数,升序)

目标是 [x, v₁, v₂, …, v_c]

对第 i 个 v(i ≥ 2),若 v_i = v_{i−1},

那么它可以"留在原位"(因为它左边也是同样的值)

所以"能不动"的个数 = 相邻相等的对数

可保留 P 个位置

3
套用 n − 循环数

剩余 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}11 ✓
样例1 第3次[160,170]168{170}11 ✓
样例1 第4次[160,168,170]165{168,170}22 ✓
样例2 第4次[20,20,20]10{20}11 ✓
⚠️
最容易错的地方:把"不同身高的种数"当成"比它高的人数"。看样例 2 第 4 次:队伍是 [20,20,20],新同学身高 10,有 3 个人比他高,但答案是 1 而不是 3——因为只要和其中一个 20 交换一次,另外两个 20 的位置就自动对了(它们本来就是 20,排在哪儿都是 20)。"相同身高的同学可以互相顶替",这就是省下交换次数的原因。
04
解法对比
去重计数 vs 模拟冒泡

⚔️ 解法对比

🟢 统计更大的不同身高数(推荐) 推荐

维护已入场同学的身高集合,每次数一数"比新同学高的不同值"有几个

  • 时间 O(NM),M ≤ 2000 时约 4 × 10⁶
  • 代码 20 行
  • 有严格推导支撑
💡
实现:用一个数组 inQ[学号] 标记是否已入场;每次询问时遍历所有已入场的同学,把"身高 > 新同学身高"的身高值去重计数。M、N ≤ 2000,双重循环完全够快。

🟠 直接模拟冒泡排序

每次插入后真的模拟排序,数交换次数

  • 容易把"交换次数"数错
  • 相邻交换与任意交换次数不同
  • 模拟逻辑复杂
  • 容易掉进陷阱
⚠️
为什么不推荐:如果按"只能交换相邻两人"来模拟,样例 2 会得到 3 而不是 1——与题目不符。而且每次排序的 O(N log N) 加起来虽不算慢,但逻辑上的坑远比"去重计数"多。

📈 性能对比

方案复杂度正确性风险
去重计数O(NM)低(有推导保证)
模拟排序O(NM log N)高(易误用相邻交换)
05
算法流程图
每次点名后统计更高的不同身高数
开始读入 N、身高数组 h[0..N−1]、Mpresent[x] 全部标记为 false处理每次点名 x把 h[x] 加入"已入场集合";cnt = 0,seen 清零遍历所有已入场同学 y:若 h[y] > h[x] 且 h[y] 首次出现,则 cnt 加 1输出 cnt结束处理下一次点名
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔁 最少交换次数计算器

第一行输入 N,第二行输入身高,第三行输入 M,随后 M 行输入点名学号。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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;
}
🔑
为什么用"去重计数"而不是"数人数"?看样例 2:队伍里有 3 个身高 20 的人,新同学身高 10。数人数会得到 3,但正确答案是 1——因为这三个 20 是"同一个身高",只需一次交换就能让新同学跨过它们(交换之后三个 20 的排列依旧有序)。注意判定用的是 h[y] > h[x](严格大于),因为身高相同的同学之间不用交换。

📖 关键几行怎么看

代码作用为什么这样写
inQ[x] = true加入队伍每次点名把该学号标记为已入场
h[y] <= h[x] → continue筛选严格大于才算"更高"
seen 去重去重计数同一身高只算一次
printf("%d\n", cnt)输出每次点名输出一行
⚠️
三个坑:① 数的是"人数"而不是"不同身高种数"(样例 2 会错);② 比较用 ≥ 而不是 >(身高相同不该计入);③ 忘记新同学加入后要立即更新集合再统计。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5
170 165 168 160 175
4
0 / 3 / 2 / 1
0
1
1
2
题面样例 1
4
20 20 20 10
4
0 / 1 / 2 / 3
0
0
0
1
题面样例 2(有相同身高)
1
100
1
0
0只有一名同学
3
10 20 30
3
2 / 1 / 0
0
1
2
每次都在末尾加一个更矮的
3
30 20 10
3
0 / 1 / 2
0
0
0
每次加入更高的,队伍保持有序
✅
自查清单:① 去重了吗?② 用严格大于吗?③ 集合更新时机对吗?

🚨 易错点清单

⚠️
数人数而非种数:相同身高的同学可以互相顶替,所以要去重计数(样例 2 会暴露这个错误)。
⚠️
比较写成 ≥:身高相同不需要交换,所以条件是严格大于。
⚠️
把交换当成"相邻交换":题目允许任意两人交换;若是相邻交换,答案会不同。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(NM)
空间复杂度
O(N)
N, M 最大
2000
运算量
约 4 × 10⁶

时间怎么算的?

空间都用在哪?

身高数组、入场标记、去重用的临时数组。

✅ 约 400 万次操作,瞬间完成。N、M ≤ 2000 很小,不需要更高级的数据结构。

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

🔗 常用技巧小抄

// 结论:答案 = 队伍中"比新同学高的不同身高种数"
// 因为:
//   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 − 循环个数任意两两交换类问题
相同值可顶替能保留更多不动位多重集排序的最小交换次数
去重计数同一值只算一次本题的关键结论
🌟
思考题:如果题目改成"每次只能交换相邻的两人",答案会是什么?(提示:那就变成"比新同学高的人数"而不是"种数"了——因为相邻交换必须一个一个越过去,每越过一个人就花一次。看样例 2:[20,20,20] 加 10,相邻交换需要 3 次,而任意交换只需 1 次。"交换的粒度"完全改变答案,读题时必须分清。)