Minimum
Inversion Number
Time
Limit: 2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others)
Total Submission(s):
9163 Accepted Submission(s):
5642
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
Sample Output
Author
CHEN, Gaoli
Source
求逆序数，这道题花了我一下午的时间去看线代，不过还好总算做出了....切克闹，切脑壳...
下 面来详细讲讲过程吧...
首先，我求出了 Simple
output 给出的 序列的 逆序数为22 这是没有错的，但是输出却为16，当时我这个小脑袋呀，真是....泪崩了呀！.
然后我就在这里纠结呀...哎，由于英语不是很好，居然没有读懂这句话的意思.....这是啥情况
，妈蛋呀！
out of the above sequences.
------>从上面的式子中找出最小的逆序数...
明白了这句话，下面就好办了..
最后就是一点要说的是...
对于逆序数，如果存在左右顶端对调，并且这个序列是连续的..
是可以总结出规律的,,
看代码就知道了。。
time 300+ms.... c++
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define maxn 5000
5 int a[maxn+100];
6 int bb[maxn+100]; //存储单个元素的逆序数
7 int main()
8 {
9 int n,i,j,tol;
10 while(scanf("%d",&n)!=EOF)
11 {
12 memset(bb,0,sizeof(bb));
13 for(i=0;i<n;i++)
14 {
15 scanf("%d",a+i);
16 for(j=i-1;j>=0;j--)
17 {
18 if(a[i]>a[j]&&bb[j]==0) break;
19 if(a[i]<a[j])bb[i]++;
20 }
21 }
22 tol=0;
23 for(i=0;i<n;i++) //求出逆序数
24 tol+=bb[i];
25 int res=tol;
26 for(i=0;i<n;i++)
27 {
28 tol+=n-2*a[i]-1 ;
29 if(res>tol)
30 res=tol;
31 }
32 printf("%d\n",res);
33 }
34
35 return 0;
36 }
HUDOJ-----1394Minimum Inversion Number,布布扣,bubuko.com
HUDOJ-----1394Minimum Inversion Number
原文：http://www.cnblogs.com/gongxijun/p/3650454.html
