Minimum Inversion Number(最小逆序数对 树状数组 HDU 1394)

Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24336    Accepted Submission(s): 14414

 

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

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)

You are asked to write a program to find the minimum inversion number out of the above sequences.

 

 

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

 

 

Output

For each case, output the minimum inversion number on a single line.

 

Sample Input

10 1 3 6 9 0 8 5 7 4 2

Sample Output

16

 

1.具体分析：

第一组：  
      序列：     1   3    6   9  0   8   5   7   4    2
      逆序对：  0   0    0   0  4   1  3   2   5    7         sum1=22
第二组：  
      序列：     3    6   9  0   8   5   7   4    2   1
      逆序对：  0    0  0  3   1   3    2   5    7   8        sum2=29

通过比较发现，一个数num的移动会使得：
   比num小的——个数减小——减少num
   比num大的——个数增加——增加n-(num-1)

总量变化就是n-2*num+1。

 2.  

   树状数组的插入函数(假设为 void insert(int x,int num) )的含义：在求逆序数这个问题中，我们的插入函数通常使用为insert( i , 1 )，即将数组A[i]的值加1 (A数组开始应该初始化为0，所以也可以理解为设置A[ i ]的值为1，即将数字i 加入到序列的意思 )。，同时维护c数组的值。

      树状数组中区间求和函数(假设函数定义为： int sum(int x ) )的含义：该函数的作用是用于求序列中小于等于数字 i 的元素的个数。这个是显而易见的，因为树状数组c 维护的是数组A的值，则该求和函数即是用于求下标小于等于 i 的数组A的和，而数组A中元素的值要么是0要么是1，所以最后求出来的就是小于等于i的元素的个数。

     假设序列开始一个数都没有，每添加一个数之前计算序列有多少数大于该数。程序中s=s+(i-sum(a[i]))就是表达的这个意思。——这样就求出了序列中一个数的逆序数。然后把a[i]加入到序列中，重复循环即可求得整个序列的。
参考：点击转到

3.注意：

   虽然题目中样例是一组数据，但题目要求的多组读入。

4.参考：点击转到

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define nmax 5005
int n;
int c[nmax];
int a[nmax];
int lowbit(int i)
{
	return i&(-i);
}
int insert(int x,int num)
{
	while(x<=n)
	{
		c[x]=c[x]+num;
		x=x+lowbit(x);
	}
}
int sum(int x)
{
	int ans=0;
	while(x)
	{
		ans=ans+c[x];
		x=x-lowbit(x);
	}
	return ans;
}
int main()
{
	while(cin>>n){
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i]++;
	}
	int s=0;
	
	for(int i=0;i<n;i++)
	{
		s=s+(i-sum(a[i]));
		insert(a[i],1);
	}
	int ans=s;
	for(int i=0;i<n;i++)
	{
		s=s+n-2*a[i]+1;
		ans=min(ans,s);
	}
	cout<<ans<<endl;
    }
	return 0;
}

      第二种方法，找相应的数字位置：9是第一大数字，3就是第7大数字，以3为例，就可以通过求前7项的和来记录3的逆序数。具体解析见下面图片：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> 
using namespace std;
#define nmax 5006
int c[5006];
int a[5006];
int n;
int lowbit(int i)
{
	return i&(-i);
}
void add(int k,int v)
{
	while(k<=n)
	{
		c[k]=c[k]+v;
		k=k+lowbit(k);
	}
}
int sum(int k)
{
	int res=0;
	while(k)
	{
		res=res+c[k];
		k=k-lowbit(k);
	}
	return res;
}
int main()
{
	int ans;
	while(scanf("%d",&n)!=EOF)
	{
		memset(c,0,sizeof(c));
		for(int i=0;i<n;i++) 
		  scanf("%d",&a[i]);
		int re=0;
		for(int i=0;i<n;i++)
		{
			re=re+sum(n-a[i]);
			add(n-a[i],1);
		}
		int tp=re;
		ans=re;
		for(int i=0;i<n-1;i++)
		{
			add(n-a[i],-1);
			tp=tp+sum(n-a[i])-a[i];
			add(n-a[i],1);
			ans=min(tp,ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}