欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-09 19:29:58
...

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的逆序数。具体解析见下面图片:

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

#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;
}