hdu 1394 Minimum Inversion Number(树状数组求逆序数)

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
题目大意:给出一个排列,可以把一个数和他之前的数字按照原来的顺序放到原来的排列末尾得到一个新的序列,问逆序对数的最少个数。
树状数组求逆序数的思路就是开一个计数数组cnt,对于当前插入的数字,计算出在他之前有多少个比他大的数字出现,也就得到这个数字的逆序对数,然后我们在这个数字的cnt上加1即可。我们可以使用树状数组快速求出有多少个比他的数字(sum(n)-sum(a)),更新的话就是add(a,1)。
对于这道题目,我们可以用树状数组预先处理出一开始给出的排列的逆序对个数。因为lowbit(0)会出错,我直接加1了。然后利用逆序数的性质:我们把第一个数移到原排列的最后一个的位置,那么逆序对数会增加n-(a[i]-1)-1对,也会相应地减少a[i]-1对。因为相当于现在对于a[i]来说,a[i]大的数都在他前面,小的数也在他的前面(而这一部分是原来在他后面的)。
然后O(n)计算出最小值即可,总复杂度O(NlogN)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注