1328：【例7.7】光榮的夢想——逆序對

【題目描述】

Prince對他在這片大陸上維護的秩序感到滿意，于是決定啟程離開艾澤拉斯。在他動身之前，Prince決定賦予King_Bette最強大的能量以守護世界、保衛這裡的平衡與和諧。在那個時代，平衡是個夢想。因為有很多奇異的物種擁有各種不穩定的能量，平衡瞬間即被打破。KB決定求助于你，幫助他完成這個夢想。

一串數列即表示一個世界的狀态。

平衡是指這串數列以升序排列。而從一串無序數列到有序數列需要通過交換數列中的元素來實作。KB的能量隻能交換相鄰兩個數字。他想知道他最少需要交換幾次就能使數列有序。

【輸入】

第一行為數列中數的個數n,第二行為n <= 10000個數。表示目前數列的狀态。

【輸出】

輸出一個整數，表示最少需要交換幾次能達到平衡狀态。

【輸入樣例】

4

2 1 4 3

【輸出樣例】

2

分析

1. 此題求的需要交換兩個數順序的交換次數，也就是求逆序對的數量，因為一個逆序對說明兩個數的位置反了，一個逆序對就交換一次，是以可以用歸并排序來解這個題。
2. 歸并排序也正是分治的思想，先不斷的将數組分成一塊一塊，然後在每兩塊合并的時候進行排序，最後合到一塊就是一個有序序列；
3. 為什麼逆序對的數量是這個式子呢ans += mid - i + 1，因為當a[i]>a[j]，此時 a[j] 與 左側數組剩餘的 mid-i+1 個數字構成逆序對 ;（說明a[j]不該放在 左側數組mid-i+1 個數字的後面，構成逆序對）；

#include<bits/stdc++.h>

using namespace std;

int n, ans;
int a[10005], temp[10005];

void merge(int l, int mid, int r) {
    int i = l;
    int j = mid + 1;
    int k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            //逆序
            ans += 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];
    }
}

void mergeSort(int l, int r) {
    if (l >= r)
        return;
    int mid = l + (r - l) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, mid, r);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    mergeSort(1, n);
    cout << ans;
}