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表示.