POJ-1804 Brainman

并归排序+求逆序对 POJ-1804 Brainman

题目链接：POJ-1804
题目大意：给定一串数字 每次交换两个相邻的数字 使之从小到大排列 就是求逆序对

解题思路：并归排序 在前面的数据大于后面的数据时加逆序对的统计（cnt+=mid-i+1;//逆序对数量 因为左面的数字一旦大于右半区一个数 那么排在左面后面（左半区）的数字也大于那个数 并不是cnt++） 最后注意最后输出两个换行。。。直接Presentation Error了

代码块：

#include<iostream>
#include<cstdio>

using namespace std;

int cnt = 0;
int n;
int arr[1009];
void mergeSort(int left,int right);
void merge(int left,int mid,int right);
int main(){
	int num;
	scanf("%d",&num);
	for(int k = 1; k <= num; k++) {	
		scanf("%d",&n);
		for(int i = 0;i<n;i++){
			scanf("%d",&arr[i]);
		}
		mergeSort(0,n-1);
		printf("Scenario #%d:\n%d\n\n",k,cnt);
		cnt = 0;
	}
	return 0;
}
void mergeSort(int left,int right){
	if(left>=right) return;
	int mid = (left + right)/2;
	mergeSort(left,mid);
	mergeSort(mid+1,right);
	merge(left,mid,right);
}
void merge(int left,int mid,int right){
	int i = left,j = mid+1,t=0;
	int newArr[right+1];
	while(i<=mid && j<=right){
		if(arr[i] > arr[j]){
			newArr[t++] = arr[j++];
			cnt+=mid-i+1;//逆序对数量 因为左面的数字一旦大于一个数 那么排在左面后面（左半区）的数字也大于那个数 并不是cnt++
		}else{
			newArr[t++] = arr[i++];
		}
	}
	while(i<=mid) newArr[t++] = arr[i++];
	while(j<=right) newArr[t++] = arr[j++];
	for(int i=0;i<t;i++){
		arr[left+i] = newArr[i];
	}
}