GESP 题解库 / 4 级题解 / [GESP202506 四级] 排序 · 第 7 / 25 题
GESP202506 四级 · B4361 · 简单

排序

每次只能交换相邻两位,求把队伍调整成"身高降序、体重降序"所需的最少交换次数。

📊
n ≤ 3000
队伍人数
🔢
h, w ≤ 10⁹
数值范围
⚡
O(n²)
时间复杂度
🎯
逆序对
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

体育课上有 n 名同学排成一队,第 i 位同学身高 hᵢ、体重 wᵢ。老师希望同学们按身高从高到低排队,身高相同则按体重从重到轻排序。

调整时每次只能交换相邻两位同学的位置。求最少需要多少次交换操作。

💡
人话翻译:这是一个经典结论题——"只允许交换相邻元素,把序列变成目标顺序所需的最少次数"恰好等于逆序对的个数。所以我们要做两件事:① 确定每个人的目标位置;② 数出原序列相对目标顺序的逆序对。

🔍 关键词提取

相邻交换逆序对稳定排序目标位置映射

已知条件

项目说明
输入第一行 n;随后 n 行每行 hᵢ、wᵢ
输出最少相邻交换次数
数据范围1 ≤ n ≤ 3000
数值范围0 ≤ hᵢ, wᵢ ≤ 10⁹
目标顺序身高降序 → 体重降序

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 最少相邻交换 = 逆序对
🧠 核心结论
相邻交换一次消除一个逆序对
最少交换次数 = 逆序对数
这是本题的理论依据
必须能自己说明
🎯 定目标位次
按 (h 降序, w 降序) 排序
相同则按原下标升序(稳定)
rank[id] = 目标位次
保证得到最小解
🔍 数逆序对
把原序映射成 rank 序列
统计 i < j 且 B[i] > B[j] 的对数
n ≤ 3000 → O(n²) 可行
9 × 10⁶ 次比较
⚠️ 易错点
排序不稳定导致答案偏大
h、w 用 int 存(会溢出)
位次数组下标搞错
相等元素的处理
03
样例手算推导
样例 5 人的位次映射与逆序对

🧮 样例 1:答案 8

原队伍(按输入顺序):

原下标身高 h体重 w
1160
2370
3280
4455
5450
1
第 1 步:按 (h 降序, w 降序) 排序

h 最大的是 4(两人):4 号 w = 55、5 号 w = 50

w 降序 → 4 号在前、5 号在后

接着是 h = 3 的 2 号、h = 2 的 3 号、h = 1 的 1 号

目标顺序:4号、5号、2号、3号、1号

目标队伍已确定

2
第 2 步:给每人标目标位次

4 号 → 第 1 位;5 号 → 第 2 位

2 号 → 第 3 位;3 号 → 第 4 位;1 号 → 第 5 位

所以 rank[1] = 5、rank[2] = 3、rank[3] = 4、rank[4] = 1、rank[5] = 2

位次数组已建好

3
第 3 步:按原顺序写出位次序列

原序 1、2、3、4、5 对应位次:5、3、4、1、2

序列 B = [5, 3, 4, 1, 2]

B = [5, 3, 4, 1, 2]

4
第 4 步:数逆序对

5 > 3、4、1、2 → 4 个

3 > 1、2 → 2 个

4 > 1、2 → 2 个

1、2 后面没有更小的 → 0 个

合计 4 + 2 + 2 = 8

✅ 输出 8

最少交换 8 次 ✓

🧮 样例 2:答案 1(考察稳定排序)

数据:4 0 / 4 0 / 2 0 / 3 0 / 1 0,其中有两个完全相同的 (4, 0)。

原下标(h, w)目标位次说明
1(4, 0)1与 2 号完全相同 → 按原顺序,1 号在前
2(4, 0)2与 1 号完全相同 → 2 号在后
3(2, 0)4
4(3, 0)3
5(1, 0)5
1
位次序列

按原顺序 1 ~ 5:位次是 1、2、4、3、5

B = [1, 2, 4, 3, 5]

B = [1, 2, 4, 3, 5]

2
数逆序对

1 后面都比它大 → 0

2 后面都比它大 → 0

4 > 3 → 1 个

3、5 后面没有更小的 → 0

✅ 输出 1

🔑
如果排序不稳定会怎样?假设把两个 (4, 0) 的位次互换了,位次序列会变成 [2, 1, 4, 3, 5],逆序对变成 1(2>1)+ 1(4>3)= 2,比正确答案多 1。因为"把 1 号同学换到 2 号后面"完全是多余的操作。相同元素必须保持原相对顺序(稳定排序),才能得到最少交换次数。
04
解法对比
O(n²) 数逆序对 vs 树状数组

⚔️ 解法对比

🟢 双重循环 O(n²)(推荐) 推荐

对每个 i,统计后面有多少个比它小的

  • 时间 O(n²)
  • n = 3000 时约 4.5 × 10⁶ 次
  • 代码 5 行
  • 不需要额外数据结构
💡
为什么够用:n ≤ 3000,双重循环最多约 450 万次比较,C++ 一秒能跑上亿次,完全不用优化。

🟠 树状数组 / 归并排序 O(n log n)

用数据结构在 O(n log n) 内统计逆序对

  • 时间 O(n log n)
  • 代码复杂(30 ~ 50 行)
  • 需要离散化(h、w 可达 10⁹)
  • 本题属于过度设计
⚠️
什么时候必须用:当 n 达到 10⁵ 时,O(n²) 会超时(10¹⁰ 次),那时必须用树状数组或归并排序。本题 n ≤ 3000 是"善意提示"——直接暴力即可。

📈 性能对比

方案本题运算量n = 10⁵ 时
双重循环约 4.5 × 10⁶约 5 × 10⁹(超时)
树状数组约 4.5 × 10⁴约 1.7 × 10⁶(可行)
05
算法流程图
定目标位次 → 映射 → 数逆序对
开始读入 n 和每个人的 (h, w),记下原下标按 (h 降序, w 降序, 原下标升序) 排序,得到目标位次 rank[]按原顺序构造位次序列 B[i] = rank[原下标 i]i 从 0 到 n−1,j 从 i+1 到 n−1B[i] > B[j] 吗?是 ✓逆序对计数器加 1否 ✗不计数输出逆序对总数结束继续枚举下一对
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 最少相邻交换次数计算器

第一行输入 n,随后 n 行每行两个数(身高 体重)。程序会给出目标位次与逆序对数。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

struct Stu {
    long long h, w;
    int id;          // 原下标(1 起)
};

// 目标顺序:身高降序 → 体重降序 → 原下标升序(决定稳定性)
bool cmp(const Stu &a, const Stu &b) {
    if (a.h != b.h) return a.h > b.h;
    if (a.w != b.w) return a.w > b.w;
    return a.id < b.id;
}

Stu s[3005];
int rankOf[3005];    // rankOf[id] = 该同学的目标位次

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", &s[i].h, &s[i].w);
        s[i].id = i;
    }

    // 排序后依次给出目标位次
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; i++) rankOf[s[i].id] = i;

    // 按原顺序写出位次序列,统计逆序对
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (rankOf[i] > rankOf[j]) ans++;
        }
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"稳定"能保证最少?两个完全相同的同学(身高体重都一样)互换位置毫无意义,交换它们只会白白增加次数。所以让它们保持原来的相对顺序(即 id 升序)就能避免这些多余交换,从而得到最小值。比较函数里最后一行 return a.id < b.id; 就是稳定性的来源。

📖 关键几行怎么看

代码作用为什么这样写
return a.h > b.h;身高降序用 > 实现从高到低
return a.id < b.id;保证稳定相同元素按原序,避免多余交换
rankOf[s[i].id] = i;记录目标位次排序后第 i 个位置,就是该同学的目标位次
if (rankOf[i] > rankOf[j]) ans++;数逆序对i < j 但位次 i 更大,说明两人顺序反了
⚠️
三个坑:① 排序时不加 id 比较,相同元素顺序随机,答案可能偏大;② h、w 可达 10⁹,必须用 long long(虽然本题只做比较不会溢出,但养成习惯);③ 把"位次序列"和"原序列"搞混,导致统计对象错误。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5
1 60 / 3 70 / 2 80 / 4 55 / 4 50
8题面样例 1
5
4 0 / 4 0 / 2 0 / 3 0 / 1 0
1题面样例 2(考察稳定排序)
1
5 5
0只有一人,无需交换
3
3 1 / 2 1 / 1 1
0已经是从高到低,无需交换
3
1 1 / 2 1 / 3 1
3完全逆序,3 人需要 3 次
4
2 1 / 2 1 / 2 1 / 2 1
0全部相同,保持原顺序即可
✅
自查清单:① 排序键是 (h 降序, w 降序, id 升序) 吗?② 位次序列是按原顺序取的吗?③ 统计的是逆序对吗?

🚨 易错点清单

⚠️
排序不稳定:不比较原下标,相同元素顺序不确定,答案可能偏大(样例 2 会输出 2 而不是 1)。
⚠️
忘了逆序对这个结论:不要真去模拟交换过程,那样复杂度是 O(n²) 的交换次数,逻辑上也更难写对。
⚠️
位次映射搞反:应该是rankOf[原下标] = 目标位次,不是反过来。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
3000
最坏运算
约 4.5 × 10⁶

时间怎么算的?

空间都用在哪?

需要存下 n 个同学和 n 个位次。

✅ 约 450 万次比较,C++ 瞬间完成。n ≤ 3000 这个范围,正是为了让我们可以放心用 O(n²)。

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

🔗 常用技巧小抄

// 结论:只允许相邻交换时,最少交换次数 = 逆序对数量
// 证明思路:
//   (1) 每次相邻交换最多让逆序对减少 1(交换相邻两元素只影响它们之间这一对)
//   (2) 只要还不是有序,就一定存在相邻逆序对,交换它可让逆序对减少 1
//   (3) 所以下界可达 -> 最少次数恰好是逆序对数

// 逆序对统计:O(n^2)
long long cnt = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] > a[j]) cnt++;

// 逆序对统计:归并排序 O(n log n)(n 很大时用)
long long mergeCount(vector<int> &v, int l, int r) { /* 分治统计 */ }

// 逆序对统计:树状数组 O(n log n)(需离散化)
// 把值域压缩到 [1, n] 后,用 BIT 统计"已出现的比我大的数的个数"

🌟 举一反三

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

能力点本题怎么用还能迁移到
逆序对相邻交换的最少次数排队、卡片排序、最少交换问题
稳定排序相同元素保持原序所有涉及"相同元素不该交换"的题
目标位次映射原下标 ↔ 位次排列变位、置换类问题
🌟
思考题:如果题目改成"允许交换任意两位(不限于相邻)",最少交换次数是多少?(提示:那种情况下答案是 n 减去"置换环的个数",与逆序对无关——所以"是否限制相邻"会完全改变解法。)