1298 车厢重组
大约 3 分钟
1298 车厢重组
【算法】 排序、冒泡排序、逆序对
【C++】 冒泡排序、一维数组
【难度】 入门
一、题目简述
有一个旧式火车站,可以用一座桥旋转 180 度来交换相邻两节车厢的位置。给定 节车厢的初始顺序(),问最少需要多少次旋转才能将车厢按编号从小到大排好。
二、解题思路
2.1 问题转化
每次旋转交换相邻两节车厢——这正是冒泡排序的操作!
最少旋转次数 = 冒泡排序中的交换次数 = 逆序对数量。
2.2 什么是逆序对?
对于数组 ,如果 且 ,则 是一个逆序对。
例如 [4, 3, 2, 1] 中:
- 4 后面有 3, 2, 1 三个比它小的 → 3 个逆序对
- 3 后面有 2, 1 两个 → 2 个
- 2 后面有 1 一个 → 1 个
- 共 6 个逆序对
所以最少需要 6 次旋转。
2.3 解法:冒泡排序计数
直接模拟冒泡排序,每次交换时 cnt++:
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
cnt++;
}
}
}时间复杂度 , 时最坏约 次比较,在 1 秒内可能刚好或略超。更优的做法是用归并排序求逆序对()或树状数组,但对于入门阶段,冒泡计数已足够理解题意。
实际上,如果 且车厢是完全逆序的(如 10000, 9999, ..., 1),逆序对数 = ,交换次数也这么多。冒泡排序在 1 秒内可能勉强,建议用更高效的方法。
2.4 归并排序求逆序对(进阶)
在归并排序的合并阶段,当左半部分的元素 大于右半部分的 时,左半部分从 开始的所有元素都大于 ,形成 mid - i + 1 个逆序对。
三、参考代码
3.1 冒泡排序版(,直观易懂)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[10005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}3.2 归并排序版(,高效)
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int a[N], tmp[N];
long long cnt; // 逆序对数可能很大!
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
tmp[k++] = a[j++];
cnt += mid - i + 1; // 核心:统计逆序对
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cnt = 0;
merge_sort(0, n - 1);
cout << cnt << endl;
return 0;
}四、复杂度分析
| 方法 | 时间 | 空间 |
|---|---|---|
| 冒泡排序 | ||
| 归并排序 |
- 冒泡版在 最坏情况下约 5000 万次交换,可能接近时限
- 归并版在 下约 万次操作,瞬间完成
五、知识扩展
5.1 冒泡排序的本质
每一轮冒泡中,最大的未归位元素会一直向右交换,直到它应该在的位置。就像气泡从水底升到水面,因此得名"冒泡排序"。
5.2 类似题目
本题和经典的「逆序对」问题完全等价,也是洛谷 P1908 的简化版。理解冒泡排序和逆序对的关系后,可以进一步学习归并排序和树状数组求逆序对的方法。
