minimum inversion number(逆序数).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 5100;
//逆序数值存放在anti中
int num[MAX];
int p[MAX], t[MAX], anti = 0;
void merge(int first, int last)
{
	int mid = (first+last)/2;
	int i1 = 0, i2 = first, i3 = mid+1;
	while(i2 <= mid && i3 <= last) {
		if(p[i2] > p[i3]) {
			t[i1++] = p[i3++];
			anti += mid-i2+1;
		}
		else t[i1++]=p[i2++];
	}
	while(i2 <= mid)     t[i1++] = p[i2++];
	while(i3 <= last)     t[i1++] = p[i3++];
	i1 = first;     i2 = 0;
	while(i2 < last-first+1)     p[i1++] = t[i2++];
}

void merge_sort(int first, int last)
{
	int mid;
	if(first<last) {
		mid = (first+last)/2;
		merge_sort(first, mid);
		merge_sort(mid+1, last);
		merge(first, last);
	}
}

int main()
{
	int n,i,j,ans;
	while(scanf("%d",&n)==1) {
		for(i=0;i<n;i++) {
			scanf("%d", p+i);
			num[i] = p[i];
		}
		anti = 0;
		merge_sort(0,n-1);
		ans = anti;
		for(i=0;i<n;i++) {
			anti += n-1 -2*num[i];
			ans = min(anti, ans);
		}
		printf("%d\n", ans);
	}
}