NTHU OJ - 7654 - PE - 交換次數

The following program is my ACcepted code for NTHU-7654.
It's a for everybody to learn and discuss.
If there is any mistake or comment, please let me know.  :D

此乃NTHU 7654的AC code!

歡迎一同討論學習，如有錯誤與任何建議請留言 : )

點這裡看題目 Click here to see this Problem!

//This program is for NTHU 7654 - PE - 交換次數
//題目來源 Problem link: http://acm.cs.nthu.edu.tw/problem.php?pid=7654

/*
跟UVA 10810 Ultra-QuickSort超級像!
只是n值不同，且n=0也不會結束。

Just like the UVa 10810,
but this is with different n range and would not be stopped when n = 0.
*/

#include<stdio.h>
#define MAX 1000001

int n[MAX];
long long int swapCount;

/* merge 2 sequence.
first is   low -> (low + high) / 2
second is (low + high)/2 + 1 -> high
*/
void merge(int low, int high)
{
    int mid = (low + high) / 2;
    int tmp[MAX], len = 0;
   
    for(int i = low, j = mid + 1; (i <= mid || j <= high);)
    {
        if(i > mid)             {tmp[len] = n[j]; len++; j++;}
        else if(j > high)       {tmp[len] = n[i]; len++; i++;}
        else if(n[i] <= n[j])   {tmp[len] = n[i]; len++; i++;}
        else if(n[i] > n[j])    {tmp[len] = n[j]; len++; j++; swapCount += (mid - i +1);}
        //重要!!~翻轉的次數=後面數列的數字有幾次小於前面數列中的數字
    }

    for(int i = low, j = 0; i <= high; i++, j++)
        n[i] = tmp[j];

    return;
}

//first divide the array into 2 parts, and then merge
void mergeSort(int low, int high)
{
    if(low >= high)
        return;
   
    mergeSort(low, (low + high) / 2);
    mergeSort((low + high)/2 + 1, high);
   
    //printf("low: %d   high: %d\n", low, high);
    merge(low, high);
    return;
}

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

Please feel free to use it after adding this blog as an reference. (http://autekroy.blogspot.tw) If there is any mistake or comment, please let me know. :D 

歡迎使用與分享任何內容，但請記得標示此部落格為出處。(http://autekroy.blogspot.tw/) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )