洛谷P1116车厢重组:题解和思路

车厢重组题解

嘿嘿！今天我们来一起当“火车站职工”，看看如何通过一座神奇的桥，把乱成一锅粥的车厢，重新排成整齐的顺序吧！这个任务看起来容易，实则暗藏玄机，每次只能通过桥交换相邻的两节车厢，是不是让你想起了某个排序算法？没错，这就是经典的冒泡排序问题！

原题

思路分析

每次只能交换相邻的两节车厢，这不就是冒泡排序的交换操作吗？不过，我们不需要真的去模拟整个冒泡排序，而是可以通过计算“逆序对”的数量来解决问题。

什么是逆序对？

逆序对就是两节车厢i和j，如果i在j前面但i的编号比j大，那么它们就形成了一个逆序对。比如车厢顺序是4 3 2 1，那么4和其他车厢就形成了多个逆序对。

为什么我们要关心逆序对呢？因为每次交换相邻车厢，都会减少一个逆序对。最少旋转次数就等于初始顺序中的逆序对总数。

如何快速计算逆序对？

暴力枚举每一对车厢可以解决问题，但这会导致O(N^2)的时间复杂度，对于最多1万个车厢来说显然太慢了。幸好有一种高效的办法，就是利用归并排序来计算逆序对，总时间复杂度为O(N \log N)。

代码实现

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

const int MAXN = 10010;
int a[MAXN], temp[MAXN];
long long cnt = 0;

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]) {
            temp[k++] = a[i++];
        } else {
            cnt += mid - i + 1; // 统计逆序对
            temp[k++] = a[j++];
        }
    }
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];
    for(int i = l; i <= r; i++) a[i] = temp[i];
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    merge_sort(0, n-1);
    cout << cnt << endl;
    return 0;
}

优劣分析

优点：

• 高效性： 利用归并排序，时间复杂度为O(N \log N)，可以轻松应对N = 10000的规模。

• 简洁明了：通过归并排序，直接在排序过程中计算逆序对，不需要额外复杂的操作。

缺点：

• 实现复杂度稍高：虽然归并排序高效，但实现细节较多，相比一些简单算法对初学者不太友好。

• 额外空间开销：在归并排序过程中，需要使用额外的数组temp来存储中间结果，可能对空间敏感的场景不太适合。

总结

通过归并排序，我们不仅能高效解决这个车厢重组问题，还能在排序过程中统计逆序对，简直是一举两得！希望这个“火车站的桥”不再成为难题啦，让我们轻松搞定车厢的排序！(￣︶￣*)

• 题解