# 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

ZOJ Monthly, January 2003

求逆序数，这道题花了我一下午的时间去看线代，不过还好总算做出了....切克闹，切脑壳...

首先，我求出了 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 }```

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 }```

0 条评论

• ### nyoj 115------城市平乱（ dijkstra // bellman ）

城市平乱 时间限制：1000 ms  |  内存限制：65535 KB 难度：4 描述 南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。 他在用这N个...

• ### Flyod 算法(两两之间的最短路径)

Flyod 算法(两两之间的最短路径) 动态规划方法，通过相邻矩阵， 然后把最后的结果存在这么一个矩阵里面，(i,j), #include <iostream...

• ### poj----1330Nearest Common Ancestors（简单LCA)

题目连接  http://poj.org/problem?id=1330 就是构建一棵树，然后问你两个节点之间最近的公共父节点是谁？ 代码： 1 /*Sour...

• ### 函数参数传递常用的三种方式

由于值传递是单向传递，传递过程中只是改变了形参的数值，并未改变实参的数值，因此并不会改变a和b原有的值。

• ### Red and Black（DFS 深搜练习）

There is a rectangular room, covered with square tiles. Each tile is colored eit...

• ### HDU 1863 畅通工程

一道很朴素的最小生成树，不过通过此题知道了，当n已经决定的情况下，若n个点无法构成最小生成树的话，最终得到ans无法得到精确的值，他会将无穷大的路径加入。 #i...

• ### 挑战程序竞赛系列（30）：3.4矩阵的幂

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### ZR18提高5解题报告

设\$f[i][j]\$表示前\$i\$个位置，前缀和为\$j\$的方案数，转移的时候该位置放了什么，以及该位置之前的和是多少。

• ### 图论建图

图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

• ### Codeforces Round #521 (Div. 3) D. Cutting Out(二分)

题目链接：http://codeforces.com/contest/1077/problem/D