紀錄一下 相關資料 與 答案

搜出來 的 資料：

GeeksForGeeks 的 答案 Number of swaps to sort when only adjacent swapping allowed:

https://www.geeksforgeeks.org/number-swaps-sort-adjacent-swapping-allowed/

Adjacent swap count 即 顛倒個數 (Inversion count) 之證明（還蠻 離散 的） Proof:

https://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps

相關問題 Related:

https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

Java 實作（O(nlogn)）（底下留言說在 Kattis 上測沒過 但好幾年了沒人說到底哪裡錯） Java implementation:

https://stackoverflow.com/questions/337664/counting-inversions-in-an-array/6424847

GeeksForGeeks 的 實作 Count Inversions in an array | Set 1 (Using Merge Sort):

https://www.geeksforgeeks.org/counting-inversions/

Kattis 上 一樣的問題 Kattis problem:

https://open.kattis.com/problems/froshweek

紙筆跑 2-3 個 Bubble sort ( 將小的往左丟/大的往右丟 ) 觀察一下 可以發現：

逐個將 各元素 左側較大/右側較小 的個數相加 即為答案，

而 左側較大/右側較小 的 個數總和 其實就是 顛倒數 (Inversion count)，

兩兩相比 前>後 的個數，

所以可以用 雙層 for 以 O(n^2) 解出。

參考答案 ( O(n^2) )：

#include<stdio.h>
#define MAXN 10000

int main(){
    int n, num[MAXN], i, j, invCount;
    while (scanf("%d", &n) != EOF) {
        for (i=0; i<n; ++i) {
            scanf("%d", &num[i]);
        }
        invCount = 0;
        for (i=0; i<n; ++i) {
            for (j=i+1; j<n; ++j) {
                if (num[i] > num[j]) {
                    ++invCount;
                }
            }
        }
        printf("%d\n", invCount);
    }
    return 0;
}

而 更快的做法 是用 merge sort，

左 inv_count + 右 inv_count + 跨左右 inv_count（merge時數），

有點 div-and-con 的感覺。

參考答案（從 GeeksForGeeks 改來）( O(nlogn) Merge sort )：

#include<stdio.h>
#define MAXN 10000

int countInv(int num[], int tmp[], int left, int right) {
    int mid, res=0;
    if (right > left) {
        mid = (left+right) / 2;
        res = countInv(num, tmp, left, mid);
        res += countInv(num, tmp, mid+1, right);
        res += merge(num, tmp, left, mid, right);
    }
    return res;
}
int merge(int num[], int tmp[], int left, int mid, int right) {
    int i=left, j=mid+1, k=left, res=0;
    while (i <= mid && j <= right) {
        if (num[i] <= num[j]) {
            tmp[k++] = num[i++];
        }
        else {
            tmp[k++] = num[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid)   { tmp[k++] = num[i++]; }
    while (j <= right) { tmp[k++] = num[j++]; }
    for (i=left; i<=right; ++i) { num[i] = tmp[i]; }
    return res;
}

int main(){
    int n, num[MAXN], tmp[MAXN], i, j;
    while (scanf("%d", &n) != EOF) {
        for (i=0; i<n; ++i) {
            scanf("%d", &num[i]);
        }
        printf("%d\n", countInv(num, tmp, 0, n-1));
    }
    return 0;
}

這麼經典的問題我竟然到今天才寫，真是怠惰啊！