poj-2299-Ultra-QuickSort

Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

정렬 되 지 않 은 수열 을 드 리 겠 습 니 다. 매번 인접 한 두 개의 수 를 바 꿀 수 있 습 니 다. 정상 적 인 오름차 로 바 꾼 후 필요 한 횟수 를 물 어보 세 요.첫 번 째 반응 은 바로 역 서열 을 구 하 는 것 입 니 다. 시간 을 보고 7000 ms 를 주 었 습 니 다. 물이 충분히 지나 간 것 같 아서 물 을 한 발 흘 렸 습 니 다. 아니 나 다 를 까 시간 이 초과 되 었 습 니 다............................................그래서 했 어 요.
이것 은 병합 정렬 입 니 다.

void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //      
        mergesort(a, mid + 1, last, temp); //      
        mergearray(a, first, mid, last, temp); //            
    }  
}  
  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(a, 0, n - 1, p);  
    delete[] p;  
    return true;  
}  

다음은 제 코드 입 니 다.

 
 
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    long long num[500005];
    long long temp[500005];
    int n;
    long long ans;

    void merge(int low, int mid, int high)
    {
        int i = low, j = mid + 1, k = low;
        while (i <= mid && j <= high)
        {
            if (num[i] <= num[j])
            {
                temp[k++] = num[i++];
            }
            else
            {
                ans += j - k ;
                temp[k++] = num[j++];
            }
        }
        while (i <= mid) temp[k++] = num[i++];
        while (j <= high) temp[k++] = num[j++];
        for (i = low; i <= high; ++i)
        {
            num[i] = temp[i];
        }
    }

    void mergeSort(int a, int b)
    {
        if (a < b)
        {
            int mid = (a + b) / 2;
            mergeSort(a, mid);
            mergeSort(mid + 1, b);
            merge(a, mid, b);
        }
    }


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