学步园

又有一段时间没怎么写博客了。是不是连这么点时间也要节约。。额。。

所谓的逆序数就是前面的数比后面的要大，在一个排列中，所有逆序数的总和就是这个排序的逆序数

比如： 2  3 4 1，逆序数有 21,，31，41，所以逆序数就是3

关键是怎么求出n个数的逆序数：

1.先求出中的逆序数

2.每次把最后面的往前调，逆序数减少 n - 1 - a[i], 增加 a[i];

详见代码：

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

int a[5050];
int main() {
	int n, sum;
	while(scanf("%d", &n) !=EOF) {
		sum=0;
		for (int i = 1; i <= n; i ++)
			scanf("%d", &a[i]);
		for (int j = 1; j <= n; j ++) {
			for (int k = j + 1; k <= n; k ++) {
				if(a[j] > a[k])
					sum ++;
			}
		}
		int ans = sum;
		for(int t = n; t >= 1; t --) {
			sum -= (n - 1 - a[t]);
			sum += a[t];
			if(ans > sum)
				ans = sum;
		}
		printf("%d\n", ans);
	}
	return 0;
}