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++ 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 5000
int a[maxn+100];
int bb[maxn+100]; //存储单个元素的逆序数
int main()
{
    int n,i,j,tol;
    while(scanf("%d",&n)!=EOF)
    {
        memset(bb,0,sizeof(bb));
        for(i=0;i<n;i++)
        {
          scanf("%d",a+i);
          for(j=i-1;j>=0;j--)
          {
              if(a[i]>a[j]&&bb[j]==0) break;
              if(a[i]<a[j])bb[i]++;
          }
        }
        tol=0;
        for(i=0;i<n;i++)  //求出逆序数
             tol+=bb[i];
             int res=tol;
        for(i=0;i<n;i++)   
        {
                tol+=n-2*a[i]-1 ;
                if(res>tol)
                    res=tol;
        }
        printf("%d
",res);
    }

    return 0;
}

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

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

运用这个原理便可以得到结果，代码如下：

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define maxn 5000
int aa[maxn+100];
int bb[maxn+100];
int nn,tol=0;
void mergec(int low ,int mid ,int hight )
{
    int i,j,k;
   int *cc = (int *)malloc(sizeof(int)*(hight-low+3));
     i=low;
     j=mid;
     k=0;
    while( i<mid&&j<hight )
    {
        if(aa[i]>aa[j])
        {
          cc[k++]=aa[j++];
          tol+=mid-i;
        }
       else
          cc[k++]=aa[i++];
    }
    for( ; i<mid ;i++)
       cc[k++]=aa[i];
    for( ; j<hight ; j++)
       cc[k++]=aa[j];
    k=0;
    for(i=low;i<hight;i++)
       aa[i]=cc[k++];
      free( cc );
}
/*用递归求解归并排序无法求逆序数*/
void merge_sort(int st,int en)
{
    int mid;
    if(st+1<en)
    {
        mid=st+(en-st)/2;
        merge_sort(st,mid);
        merge_sort(mid,en);
        mergec(st,mid,en);
    }
}
int main()
{
    int  i,res;
 // freopen("test.in","r",stdin);
    while(scanf("%d",&nn)!=EOF)
    {
          tol=0;
        for(i=0;i<nn;i++){
             scanf("%d",aa+i);
             bb[i]=aa[i];
         }
         merge_sort(0,nn);
          res=tol;
       //printf("tol=%d
",res);
         for(i=0;i<nn-1;i++)
         {
             tol+=nn-2*bb[i]-1;
             if(res>tol) res=tol;
         }
        printf("%d
",res);
    }
    return 0;
}

接下来是非递归调用....版的归并排序

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define maxn 5000
int aa[maxn+100];
int bb[maxn+100];
int nn,tol=0;
void mergec(int low ,int mid ,int hight )
{
    int i,j,k;
   int *cc = (int *)malloc(sizeof(int)*(hight-low+3));
     i=low;
     j=mid;
     k=0;
    while( i<mid&&j<hight )
    {
        if(aa[i]>aa[j])
        {
          cc[k++]=aa[j++];
          tol+=mid-i;
        }
       else
          cc[k++]=aa[i++];
    }
    for( ; i<mid ;i++)
       cc[k++]=aa[i];
    for( ; j<hight ; j++)
       cc[k++]=aa[j];
    k=0;
    for(i=low;i<hight;i++)
       aa[i]=cc[k++];
      free( cc );
}

/*----------------------华丽丽的分割线--------------------------------*/
void merge_sort( int st , int en )
{
    int s,t,i;
    t=1;
    while(t<=(en-st))
    {
        s=t;
        t=s*2;    //表示两个s的长度
        i=st;
        while(i+t<=en){
            mergec(i,i+s,i+t);
            i+=t;
        }
     if(i+s<en)
         mergec(i,i+s,en);
    }
    if(s<en-st)
         mergec(st,st+s,en);
}
int main()
{
    int  i,res;
//  freopen("test.in","r",stdin);
    while(scanf("%d",&nn)!=EOF)
    {
          tol=0;
        for(i=0;i<nn;i++){
             scanf("%d",aa+i);
             bb[i]=aa[i];
         }
         merge_sort(0,nn);
          res=tol;
       //printf("tol=%d
",res);
         for(i=0;i<nn-1;i++)
         {
             tol+=nn-2*bb[i]-1;
             if(res>tol) res=tol;
         }
        printf("%d
",res);
    }
    return 0;
}

 用树状数组...

代码：

/*
用树状数组求逆序数
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 5000
int aa[maxn+100];
int bb[maxn+100];
int nn;
int lowbit(int k)
{
   return k&(-k);
}
void ope(int x)
{
    while(x<=nn)
    {
      aa[x]++;
      x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=aa[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{

    int i,res,ans;
    //freopen("test.in","r",stdin);
    while(scanf("%d",&nn)!=EOF)
    {
       memset(aa,0,sizeof(aa));
       res=0;
       for(i=0;i<nn;i++)
       {
         scanf("%d",&bb[i]);
         res+=sum(nn)-sum(bb[i]+1);
         ope(bb[i]+1);
       }
       ans=res;
       for(i=0;i<nn;i++)
       {
           res+=nn-1-2*bb[i];
           if(ans>res)
                  ans=res;
       }
       printf("%d
",ans);
   }
  return 0;
}