1394 minimum inversion number.cpp

来自「ACM 威士忌部分答案」· C++ 代码 · 共 30 行

#include <cstdio>
using namespace std;
int num[5001];
int imin,n;

int main()
{
	int i,j,t;
	
	while( scanf("%d",&n)!=EOF )//输入的数字范围 0 ~ n-1 
	{
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		imin=0;	
		for(i=1;i<n;i++)
			for(j=i-1;j>=0;j--)
				if(num[i] < num[j])
					imin++;
		t=imin;
		for(i=0;i<n;i++)
		{
			//t += 2*num[i]-n+1; //从尾移到头 
			t += n-2*num[i]-1; //从头移到尾 
			imin= imin > t ? t : imin;
		}
		printf("%d\n",imin);
	}
	return 0;
}