HUDOJ-----1394Minimum Inversion Number
HUDOJ-----1394Minimum Inversion Number
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
10 1 3 6 9 0 8 5 7 4 2
Sample Output
16
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 }运用递归调用版的归并排序
比如 5 4 3 2 1 《5 ，4》，《3 ，2》 --》+ 2
4 5 2 3 1
4 5 2 3 ---》 2 +2=4；
2 3 4 5 1 --》 4
10
运用这个原理便可以得到结果，代码如下：
1 #include<string.h>
2 #include<stdlib.h>
3 #include<stdio.h>
4 #define maxn 5000
5 int aa[maxn+100];
6 int bb[maxn+100];
7 int nn,tol=0;
8 void mergec(int low ,int mid ,int hight )
9 {
10 int i,j,k;
11 int *cc = (int *)malloc(sizeof(int)*(hight-low+3));
12 i=low;
13 j=mid;
14 k=0;
15 while( i<mid&&j<hight )
16 {
17 if(aa[i]>aa[j])
18 {
19 cc[k++]=aa[j++];
20 tol+=mid-i;
21 }
22 else
23 cc[k++]=aa[i++];
24 }
25 for( ; i<mid ;i++)
26 cc[k++]=aa[i];
27 for( ; j<hight ; j++)
28 cc[k++]=aa[j];
29 k=0;
30 for(i=low;i<hight;i++)
31 aa[i]=cc[k++];
32 free( cc );
33 }
34 /*用递归求解归并排序无法求逆序数*/
35 void merge_sort(int st,int en)
36 {
37 int mid;
38 if(st+1<en)
39 {
40 mid=st+(en-st)/2;
41 merge_sort(st,mid);
42 merge_sort(mid,en);
43 mergec(st,mid,en);
44 }
45 }
46 int main()
47 {
48 int i,res;
49 // freopen("test.in","r",stdin);
50 while(scanf("%d",&nn)!=EOF)
51 {
52 tol=0;
53 for(i=0;i<nn;i++){
54 scanf("%d",aa+i);
55 bb[i]=aa[i];
56 }
57 merge_sort(0,nn);
58 res=tol;
59 //printf("tol=%d\n",res);
60 for(i=0;i<nn-1;i++)
61 {
62 tol+=nn-2*bb[i]-1;
63 if(res>tol) res=tol;
64 }
65 printf("%d\n",res);
66 }
67 return 0;
68 }接下来是非递归调用....版的归并排序
1 #include<string.h>
2 #include<stdlib.h>
3 #include<stdio.h>
4 #define maxn 5000
5 int aa[maxn+100];
6 int bb[maxn+100];
7 int nn,tol=0;
8 void mergec(int low ,int mid ,int hight )
9 {
10 int i,j,k;
11 int *cc = (int *)malloc(sizeof(int)*(hight-low+3));
12 i=low;
13 j=mid;
14 k=0;
15 while( i<mid&&j<hight )
16 {
17 if(aa[i]>aa[j])
18 {
19 cc[k++]=aa[j++];
20 tol+=mid-i;
21 }
22 else
23 cc[k++]=aa[i++];
24 }
25 for( ; i<mid ;i++)
26 cc[k++]=aa[i];
27 for( ; j<hight ; j++)
28 cc[k++]=aa[j];
29 k=0;
30 for(i=low;i<hight;i++)
31 aa[i]=cc[k++];
32 free( cc );
33 }
34
35 /*----------------------华丽丽的分割线--------------------------------*/
36 void merge_sort( int st , int en )
37 {
38 int s,t,i;
39 t=1;
40 while(t<=(en-st))
41 {
42 s=t;
43 t=s*2; //表示两个s的长度
44 i=st;
45 while(i+t<=en){
46 mergec(i,i+s,i+t);
47 i+=t;
48 }
49 if(i+s<en)
50 mergec(i,i+s,en);
51 }
52 if(s<en-st)
53 mergec(st,st+s,en);
54 }
55 int main()
56 {
57 int i,res;
58 // freopen("test.in","r",stdin);
59 while(scanf("%d",&nn)!=EOF)
60 {
61 tol=0;
62 for(i=0;i<nn;i++){
63 scanf("%d",aa+i);
64 bb[i]=aa[i];
65 }
66 merge_sort(0,nn);
67 res=tol;
68 //printf("tol=%d\n",res);
69 for(i=0;i<nn-1;i++)
70 {
71 tol+=nn-2*bb[i]-1;
72 if(res>tol) res=tol;
73 }
74 printf("%d\n",res);
75 }
76 return 0;
77 }用树状数组...
代码：
1 /*
2 用树状数组求逆序数
3 */
4 #include<stdio.h>
5 #include<string.h>
6 #include<stdlib.h>
7 #define maxn 5000
8 int aa[maxn+100];
9 int bb[maxn+100];
10 int nn;
11 int lowbit(int k)
12 {
13 return k&(-k);
14 }
15 void ope(int x)
16 {
17 while(x<=nn)
18 {
19 aa[x]++;
20 x+=lowbit(x);
21 }
22 }
23 int sum(int x)
24 {
25 int ans=0;
26 while(x>0)
27 {
28 ans+=aa[x];
29 x-=lowbit(x);
30 }
31 return ans;
32 }
33 int main()
34 {
35
36 int i,res,ans;
37 //freopen("test.in","r",stdin);
38 while(scanf("%d",&nn)!=EOF)
39 {
40 memset(aa,0,sizeof(aa));
41 res=0;
42 for(i=0;i<nn;i++)
43 {
44 scanf("%d",&bb[i]);
45 res+=sum(nn)-sum(bb[i]+1);
46 ope(bb[i]+1);
47 }
48 ans=res;
49 for(i=0;i<nn;i++)
50 {
51 res+=nn-1-2*bb[i];
52 if(ans>res)
53 ans=res;
54 }
55 printf("%d\n",ans);
56 }
57 return 0;
58 }