HDU 1394 Minimum Inversion Number（求逆序对+线段树||归并排序）

淡淡的烟草味﹌ 2022-06-13 09:14 150阅读 0赞

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

解题思路：

求逆序对的进阶版，这是线段树专题，我一开始就用归并排序ac了比他们都快hhhhh，不过线段树还是要好好学的，百度搜了一个解法，可惜没备注，理解了我一个下午，加上我自己理解把代码奉上吧，不知道有没有理解对，引用：逆序数求得之后，把第一个数移到最后的逆序数是可以直接得到的，比如原来的逆序数是ans,把a\[0\]移到最后后，减少逆序数a\[0\]，同时增加逆序数n-a\[0\]-1个，就是ans-a\[0\]+n-a\[0\]-1，然后循环求最小值就行了。

代码：

先是归并排序，花的时间居然比线段树少：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    using namespace std;
    int a[5005],b[5005],n,ans;
    void Merge(int l,int r,int mid)
    {
        int t[5005],i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(a[i]>a[j])
            {
                t[k]=a[j];
                ans+=mid-i+1;
                k++;
                j++;
            }
            else
            {
                t[k]=a[i];
                i++;
                k++;
            }
        }
        while(i<=mid)
        {
            t[k]=a[i];
            k++;
            i++;
        }
        while(j<=r)
        {
            t[k]=a[j];
            k++;
            j++;
        }
        for(i=l;i<=r;i++)
            a[i]=t[i];
    }
    void guibin(int l,int r)
    {
        if(l>=r)
            return;
        int mid=(l+r)/2;
        guibin(l,mid);
        guibin(mid+1,r);
        Merge(l,r,mid);
    }
    int main()
    {
        int i,j;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                b[i]=a[i];
            }
            ans=0;
            guibin(1,n);
            int minn=ans;
            for(i=1;i<=n;i++)
            {
                ans+=n-b[i]-b[i]-1;
                if(ans<minn)
                    minn=ans;
            }
            printf("%d\n",minn);
        }
        return 0;
    }

然后是线段树代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    using namespace std;
    struct node
    {
        int l,r;
        int num;
    }t[20005];//线段树大小等于数据范围*4
    int a[5005],n;
    void Build(int l,int r,int num)//递归建树
    {
        t[num].l=l;
        t[num].r=r;
        t[num].num=0;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    int Find(int num,int x,int y)//访问函数，查找[x,y]区间内有多少已经存在的数
    {
        int l=t[num].l;
        int r=t[num].r;
        if(l==x&&r==y)
        {
            return t[num].num;
        }
        int mid=(l+r)/2;
        int s=0;
        if(x<=mid)
            s+=Find(num*2,x,min(y,mid));//如果一部分线段在t[num]的左边，访问左区间
        if(y>mid)
            s+=Find(num*2+1,max(mid+1,x),y);//如果一部分线段在t[num]的右边，访问右区间
        return s;
    }
    void update(int num,int x)
    {
        t[num].num++;//把包含x的所有区间的数目加一
        int l=t[num].l;
        int r=t[num].r;
        if(l==r)
        {
            return;
        }
        int mid=(l+r)/2;
        if(x<=mid)
            update(num*2,x);
        else
            update(num*2+1,x);
    }
    int main()
    {
        int i,j,ans;
        while(scanf("%d",&n)!=EOF)
        {
            ans=0;
            Build(1,n,1);
            for(i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                ans+=Find(1,1,a[i]+1);//在[1,a[i]+1]区间内查找之前已经存在了的比a[i]小的数的和,a[i]+1是因为从0开始
                update(1,a[i]+1);//添加了一个节点以后线段树的区间更新
            }
            ans=n*(n-1)/2-ans;//所有可能对数减去顺序对数为逆序对数
            int minn=ans;
            for(i=1;i<=n;i++)
            {
                ans+=n-a[i]-a[i]-1;//由推出的公式求出后面的逆序对数
                if(ans<minn)
                    minn=ans;
            }
            printf("%d\n",minn);
        }
        return 0;
    }

逆序数求得之后，把第一个数移到最后的逆序数是可以直接得到的。

比如原来的逆序数是ans,把a\[0\]移到最后后，减少逆序数a\[0\]，同时增加逆序数n-a\[0\]-1个

就是ans-a\[0\]+n-a\[0\]-1;

只要i从0-n-1循环一遍取最小值就可以了。