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

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 }

运用递归调用版的归并排序

比如 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2806
来自专栏ml

HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

3294
来自专栏ml

hdu---1024Max Sum Plus Plus(动态规划)

Max Sum Plus Plus Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

32710
来自专栏小樱的经验随笔

HDU 1000 A + B Problem(指针版)

A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2744
来自专栏小樱的经验随笔

HDU 3783 ZOJ

ZOJ Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

2876
来自专栏算法修养

HOJ 2226&POJ2688 Cleaning Robot(BFS+TSP(状态压缩DP))

Cleaning Robot Time Limit: 1000MS Memory Limit: 65536K Total Submission...

2934
来自专栏开发与安全

90% of python in 90 minutes

注:本文整理自 http://www.slideshare.net/MattHarrison4/learn-90 -----------------------...

2180
来自专栏小樱的经验随笔

HDU 1002 A + B Problem II(高精度加法(C++/Java))

A + B Problem II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3...

3667
来自专栏cmazxiaoma的架构师之路

你真的了解Spring MVC处理请求流程吗?

3194
来自专栏java、Spring、技术分享

深入分析Spring MVC中RequestBody与ResponseBody

  在SpringMVC中,可以使用@RequestBody和@ResponseBody两个注解,分别完成请求报文到对象和对象到响应报文的转换。在Sprin...

2581

扫码关注云+社区

领取腾讯云代金券