poj-2299 Ultra—QuickSort（歸並排序求逆序數）

Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 38688 Accepted: 13950

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 sZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIuIEZvciB0aGUgaW5wdXQgc2VxdWVuY2UgPGJyPgo8Y2VudGVyPjkgMSAwIDUgNCAsPC9jZW50ZXI+Cjxicj4KVWx0cmEtUXVpY2tTb3J0IHByb2R1Y2VzIHRoZSBvdXRwdXQgPGJyPgo8Y2VudGVyPjAgMSA0IDUgOSAuPC9jZW50ZXI+Cjxicj4KWW91ciB0YXNrIGlzIHRvIGRldGVybWluZSBob3cgbWFueSBzd2FwIG9wZXJhdGlvbnMgVWx0cmEtUXVpY2tTb3J0IG5lZWRzIHRvIHBlcmZvcm0gaW4gb3JkZXIgdG8gc29ydCBhIGdpdmVuIGlucHV0IHNlcXVlbmNlLgo8cCBjbGFzcz0="pst">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

思路：

歸並排序求逆序數，用作模版

代碼：

#include 
#define lld I64d
#define LL __int64
#define N 1000050

LL num[N];
LL temp[N];  // 歸並排序的輔助數組
LL count = 0;

void Merge(LL * array, int first, int middle, int last)
{
	int i = first, j = middle + 1, cur = 0;
	while(i <= middle && j <= last){
		if(array[i] < array[j])
			temp[cur ++] = array[i ++];
		else{
			temp[cur ++] = array[j ++];
			count += middle - i + 1;
		}
	}
	while(i <= middle)
		temp[cur ++] = array[i ++];
	while(j <= last)
		temp[cur ++] = array[j ++];

	for (int k = 0; k < cur; k ++)
		array[first ++] = temp[k];
}

void MergeSort(LL *array, int first, int last)
{
	if (first == last)
		return ;
	
	int middle = first + (last - first) / 2;
	MergeSort(array, first, middle);
	MergeSort(array, middle+1, last);
	Merge(array, first, middle, last);
}

int main()
{
	int n, i;
	while(scanf("%d", &n), n){
		count = 0;
		for(i = 0; i < n; i ++)
			scanf("%lld", &num[i]);
		MergeSort(num, 0, n - 1);
	/*	for(i = 0; i < n; i ++)
			printf("%lld ", num[i]);
		printf("\n"); */
		printf("%lld\n", count);
	}

	return 0;
}