08-18 03:59 阅读 46

关注

树状数组求正序数与逆序数hdu Minimum Inversion Number

/*
数组初始化为0后
插入1
统计的即为正序数
C(n,2)-正序数为逆序数
又题意求的为最小的逆序数
且变换规则为
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
a1后有an-a1个比a1大的，（a1-1）个比a1小的(-1指本身),然后求解
ans+=(n-a1)-(a1-1)
*/
#include<stdio.h>
#include<string.h>
#define MAXN 5050
int c[MAXN];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void update(int i,int val)
{
	while(i<=n)
	{
		c[i]+=val;
		i+=lowbit(i);
	}
}
int query(int i)
{	
	int s=0;
	while(i>0)
	{
		s+=c[i];
		i-=lowbit(i);
	}
	return s;
}
int a[MAXN];
int main()
{
	int i;
	while(scanf("%d",&n)!=EOF)
	{
		int ans=0;
		memset(c,0,sizeof(c));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			a[i]++;
			ans+=query(a[i]);
			update(a[i],1);
		}
		int min=n*(n-1)/2-ans;
		ans=min;//这个地方之前没注意到一直WA
		for(i=1;i<=n;i++)
		{
			ans+=n-a[i]-(a[i]-1);
			if(ans<min)
				min=ans;
		}
		printf("%d\n",min);
	}
	return 0;
}