poj-2299 Ultra―QuickSort（归并排序求逆序数） - c++编程基础

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.2cto.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

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;
}