UVa10810 - Ultra-QuickSort

題目大意:

排序一個數組，但只能左右交換，試問數組最少要交換幾次。

分析:

這題真的好賤，上面寫著 QuickSort 結果是 MergeSort， 這代表經驗真的還是只能相信，不能先入為主阿

QuickSort 是在每一次分治 (divide) 的時候，就已經分好大小邊，
但 MergeSort 是不斷分治，直到不能再做分治後，才開始進行排序，透過此優點，所以很容易推算出左右交換的次數，加上 MergeSort 的複雜度也跟 QuickSort 一樣，所以一樣可以完成此問題！

需要注意的點是: 由於他最大的是 500050 ， 最複雜的排序可能來到 O ( \({n^2}\) )， 所以要使用 long long 以防溢位(overflow) 。

MergeSort - Abdul Bari

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define ll long long int
using namespace std;
int intNum[500050] , intTemp[500050] ;


ll merge_sort(int l , int r){
    //debug
    //cout << l << ' ' << r << '\n';

    if(l >= r)
        return 0 ;
    ll L , R ;
    L = merge_sort(l , (r+l)/2) ;
    R = merge_sort( (r+l) /2 +1 , r );
    int intP_Start , intQ_Start , intP_End , intPosition ;
    intP_Start = l ;
    intP_End = (r+l) /2 ;
    intQ_Start = intP_End +1 ;
    intPosition = l ;
    while(intPosition <= r ){
        if(intQ_Start <= r && (intP_Start > intP_End || intNum[intQ_Start] < intNum[intP_Start] ) ){
            intTemp[intPosition++] = intNum[intQ_Start++] ;
            L += intP_End - intP_Start + 1 ;
        }
        else
            intTemp[intPosition++] = intNum[intP_Start++] ;
    }

    for(int i = l ; i <= r ; i++)
        intNum[i] = intTemp[i] ;

    //debug
    //for(int i = 0 ; i < 10 ; i++)
    //    cout << intNum[i] << ' ' ;
    //cout << '\n' ;
    return L + R ;

}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    int n ;
    while(cin >> n && n ){
        for(int i = 0 ; i < n ; i++)
            cin >> intNum[i] ;
        cout << merge_sort(0 , n-1 ) << '\n' ;
    }

    return 0;
}