每次只能交换相邻两位,求把队伍调整成"身高降序、体重降序"所需的最少交换次数。
体育课上有 n 名同学排成一队,第 i 位同学身高 hᵢ、体重 wᵢ。老师希望同学们按身高从高到低排队,身高相同则按体重从重到轻排序。
调整时每次只能交换相邻两位同学的位置。求最少需要多少次交换操作。
相邻交换逆序对稳定排序目标位置映射
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;随后 n 行每行 hᵢ、wᵢ |
| 输出 | 最少相邻交换次数 |
| 数据范围 | 1 ≤ n ≤ 3000 |
| 数值范围 | 0 ≤ hᵢ, wᵢ ≤ 10⁹ |
| 目标顺序 | 身高降序 → 体重降序 |
原队伍(按输入顺序):
| 原下标 | 身高 h | 体重 w |
|---|---|---|
| 1 | 1 | 60 |
| 2 | 3 | 70 |
| 3 | 2 | 80 |
| 4 | 4 | 55 |
| 5 | 4 | 50 |
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号
目标队伍已确定
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
位次数组已建好
原序 1、2、3、4、5 对应位次:5、3、4、1、2
序列 B = [5, 3, 4, 1, 2]
B = [5, 3, 4, 1, 2]
5 > 3、4、1、2 → 4 个
3 > 1、2 → 2 个
4 > 1、2 → 2 个
1、2 后面没有更小的 → 0 个
合计 4 + 2 + 2 = 8
✅ 输出 8
最少交换 8 次 ✓
数据: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 ~ 5:位次是 1、2、4、3、5
B = [1, 2, 4, 3, 5]
B = [1, 2, 4, 3, 5]
1 后面都比它大 → 0
2 后面都比它大 → 0
4 > 3 → 1 个
3、5 后面没有更小的 → 0
✅ 输出 1
对每个 i,统计后面有多少个比它小的
用数据结构在 O(n log n) 内统计逆序对
| 方案 | 本题运算量 | n = 10⁵ 时 |
|---|---|---|
| 双重循环 | 约 4.5 × 10⁶ | 约 5 × 10⁹(超时) |
| 树状数组 | 约 4.5 × 10⁴ | 约 1.7 × 10⁶(可行) |
第一行输入 n,随后 n 行每行两个数(身高 体重)。程序会给出目标位次与逆序对数。
点按钮开始 →
#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(虽然本题只做比较不会溢出,但养成习惯);③ 把"位次序列"和"原序列"搞混,导致统计对象错误。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 8 | 题面样例 1 |
5 | 1 | 题面样例 2(考察稳定排序) |
1 | 0 | 只有一人,无需交换 |
3 | 0 | 已经是从高到低,无需交换 |
3 | 3 | 完全逆序,3 人需要 3 次 |
4 | 0 | 全部相同,保持原顺序即可 |
rankOf[原下标] = 目标位次,不是反过来。需要存下 n 个同学和 n 个位次。
✅ 约 450 万次比较,C++ 瞬间完成。n ≤ 3000 这个范围,正是为了让我们可以放心用 O(n²)。
// 结论:只允许相邻交换时,最少交换次数 = 逆序对数量 // 证明思路: // (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 减去"置换环的个数",与逆序对无关——所以"是否限制相邻"会完全改变解法。)