【洛谷】P1116 車廂重組

題目位址：

https://www.luogu.com.cn/problem/P1116

題目描述：

在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水準旋轉。一個車站的職工發現橋的長度最多能容納兩節車廂，如果将橋旋轉 180 180 180度，則可以把相鄰兩節車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負責用這座橋将進站的車廂按車廂号從小到大排列。他退休後，火車站決定将這一工作自動化，其中一項重要的工作是編一個程式，輸入初始的車廂順序，計算最少用多少步就能将車廂排序。

輸入格式：

共兩行。第一行是車廂總數 N ( ≤ 10000 ) N( \le 10000) N(≤10000)。第二行是 N N N個不同的數表示初始的車廂順序。

輸出格式：

一個整數，最少的旋轉次數。

題目的本質是，給定一個正整數序列，隻允許交換相鄰數字的順序，問至少交換多少次，可以将整個序列排好序。這道題本質上是求逆序對個數（逆序對指某兩個數字大數排在小數之前）。而求逆序對個數，有個經典的算法，也就是歸并排序。代碼如下：

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int n;
int a[N], tmp[N];
int res = 0;  

void merge(int l, int mid, int r) {
    int i = l, j = mid + 1;
    int idx = l;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) tmp[idx++] = a[i++];
        else { 
            // 此時a[i]直到a[mid]都與a[j]産生了逆序對
            res += mid - i + 1; 
            tmp[idx++] = a[j++];
        }

    while (i <= mid) tmp[idx++] = a[i++];
    while (j <= r) tmp[idx++] = a[j++];

    for (int k = l; k <= r; k++) a[k] = tmp[k];
}

void merge_sort(int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l >> 1);
    merge_sort(l, mid), merge_sort(mid + 1, r);
    merge(l, mid, r);
}

int main() {
    cin >> n;
    for (int i = 0; i < N; ++i) cin >> a[i];

    merge_sort(0, n - 1);

    cout << res << endl;

    return 0;
}
           

時間複雜度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，空間複雜度 O ( n ) O(n) O(n)，歸并時需要個臨時數組。

算法正确性證明：

首先證明最小交換次數 r r r确實等于逆序對總數 s s s：

由于交換相鄰兩個數，逆序對至多減少 1 1 1個，而逆序對數等于 0 0 0等價于已經由小到大排好序，是以 r ≥ s r\ge s r≥s。由冒泡排序的過程知道，我們可以做到每次交換相鄰兩個數，都使得逆序數減少 1 1 1，是以 r r r是可以取到 s s s的。是以 r = s r=s r=s。

其次證明，上述歸并排序的過程，的确算出了逆序對數。先證明每次歸并的時候， r e s res res都計入了目前被歸并序列的逆序數。設 f ( x 1 , x 2 , . . . , x n ) f(x_1,x_2,...,x_n) f(x1​,x2​,...,xn​)為向量 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1​,x2​,...,xn​)的逆序對總數，容易證明遞推式： f ( x 1 , x 2 , . . . , x n ) = f ( x 1 , . . . , x i − 1 ) + f ( x i , . . . , x n ) + ∣ { ( x j , x k )   ∣   x j > x k ,   1 ≤ j ≤ i − 1 < k ≤ n } ∣ f(x_1,x_2,...,x_n)=f(x_1,...,x_{i-1})+f(x_{i},...,x_n)+\\|\{(x_j,x_k)\ |\ x_j>x_k,\ 1\le j\le i-1 < k \le n\}| f(x1​,x2​,...,xn​)=f(x1​,...,xi−1​)+f(xi​,...,xn​)+∣{(xj​,xk​) ∣ xj​>xk​, 1≤j≤i−1<k≤n}∣符号說明：對于集合 S S S， ∣ S ∣ |S| ∣S∣表示 S S S中元素個數。而在每次歸并的時候，右邊前兩項都為 0 0 0，而第三項可以在歸并的時候統計：如果index1指向的數小于等于index2指向的數，那麼沒有産生逆序，否則index1直到mid的數都與index2指向的數産生了逆序對，産生出mid-index1+1個逆序對。每次歸并完成後，所歸并的那一段序列的逆序對全被消滅，說明了所有逆序對的計數都含在了變量res裡。

現在可以證明算法的正确性了。先證明merge_sort函數将[left,right]之間的數的逆序數計入了res，并将區間内數排好序。對區間内數的數量做歸納。當隻有 1 1 1個數的時候，結論正确。假設對 1 , . . . , n − 1 1,..., n-1 1,...,n−1結論都正确，當區間内有 n n n個數的時候，由于[left,mid]和[mid+1,right]内個數都嚴格小于 n n n，由歸納假設，對左右兩半邊做merge_sort後，都達到了效果，再加上merge函數計入了分屬兩半邊的數産生的逆序數，就得到了總逆序數。由數學歸納法，是以結論對任何 n n n都成立。正确性也得到了證明。

複雜度證明可以由Master定理得到。