2098.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2098 on 2005-10-06 at 18:20:06 */ 
#include <cstdio>
#define  MAX  500000

double change;
long b[MAX];

void mergeSort(long*, long, long);
void merge(long*, long, long, long);

int main()
{
	long a[MAX], n, i;
	
	while(scanf("%ld", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			for(i = 0; i < n; i++) {
				scanf("%ld", &a[i]);
			}
			change = 0;
			mergeSort(a, 0, n-1);
			printf("%.0lf\n", change);
		}
	}
	
	return 0;
}

void mergeSort(long *a, long first, long last)
{
	long long mid = 0;
	
	if(first < last) {
		mid = (first + last) / 2;
		mergeSort(a, first, mid);
		mergeSort(a, mid+1, last);
		merge(a, first, mid, last);
	}
}
void merge(long *a, long p, long q, long r)
{
	long i, j = 0;
	long beginA = p, endA = q, beginB = q+1, endB = r;
	
	while(beginA <= endA && beginB <= endB) {
		if(a[beginA] <= a[beginB]) {
			b[j++] = a[beginA++];
		} else {
			b[j++] = a[beginB++];
			change += q - beginA + 1;
		}
	}
	while(beginA <= endA) {
		b[j++] = a[beginA++];
	}
	while(beginB <= endB) {
		b[j++] = a[beginB++];
	}
	for(i = 0; i < j; i++) {
		a[p+i] = b[i];
	}
}