程式碼備份區

題意：

給你一些數字，問說由小排到大的話最少需要兩兩交換(隔壁)幾次

解法：

基本上這題就是算inversion pair，由於數量會到百萬，所以得要用merge sort的做法去處理

然後最慘的情況是 C(n,2)個inversion pair (當順序剛好完全相反時)，所以答案可能會超過int範圍

程式碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int num[10000010];
int a[10000010];
int b[10000010];
int n;
long long int ans;

void merge(int s,int m,int e){
    int i,j;
    for(i=s;i<=m;++i)a[i] = num[i];
    for(j=m+1;j<=e;++j)b[j] = num[j];
    for(i=s,j=m+1;i<=m&&j<=e;){
        if(a[i]<=b[j])num[s++] = a[i++];
        else {
            num[s++] = b[j++];
            ans += m-i+1;
        }
    }
    while(i<=m) num[s++] = a[i++];
    while(j<=e) num[s++] = b[j++];
}

void mergeSort(int s,int e){
    if(s>=e)return ;
    int m = (s+e)/2;
    mergeSort(s,m);
    mergeSort(m+1,e);
    merge(s,m,e);
}

int main(){
    int i;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;++i){
            scanf("%d",&num[i]);
        }
        ans = 0;
        mergeSort(0,n-1);
        printf("%lld\n",ans);
    }
}