POJ 2299.Ultra-QuickSort

題目:http://poj.org/problem?id=2299

AC代碼(C++):

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#include <string.h>
#include <bitset>

#define INF 0xfffffff
#define MAXN 2005

using namespace std;

long long step;
long long num[500005];
long long temp[500005];

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   
        {  
            step += 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(){
	int n;
	while(cin>>n){
		if(n==0)break;
		step = 0;
		for(int i = 0; i < n; i++)scanf("%lld",&num[i]);
		mergeSort(0,n-1);
		cout<<step<<endl;
	}
}
           

總結: 求交換次數, 其實就是求逆序數. 用歸并排序可以快速求出逆序數. 注意這題數組大小可以大到50W, 則逆序數最大可以為n(n-1)/2=124999750000, 超過了int範圍, 若答案用int表示就會WA, 是以用long long表示.