归并排序求逆序数(POJ 1804,POJ 2299,HDU 4911)

首先,明确两个概念:

逆序对:数列a[1],a[2],a[3]…中的任意两个数a[i],a[j] (i<j),如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对.

逆序数:一个数列中逆序对的总数.

例题一:POJ 1804.   点击打开链接

解题思路:每次交换只能减少一个逆序,而且必定能减少一个逆序,从而问题就转换为求逆序个数了。这题数据规模很小,暴力可过。

我这里提供了用Merge_sort的方法求解逆序数,时间复杂度为O(nlogn).

关于归并排序:归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,r]分别进行归并排序,然后再将这两半合并起来。

在合并的过程中(设l<=i<=mid,mid+1<=j<=r),当a[i]<=a[j]时,并不产生逆序数;当a[i]>a[j]时,在前半部分中比a[i]大的数都比a[j]大,将a[j]放在a[i]前面的话,逆序数要加上mid+1-i。因此,可以在归并排序中的合并过程中计算逆序数。

#include<cstdio>
#define N 1000+10

int ans=0;
int f[N],t[N];
void Merge(int l,int m,int r) //左右两个表合并成一个表
{
    int i=l,j=m+1,cnt=0;
    while(i<=m && j<=r)
    {
        if(f[i]<=f[j])
            t[cnt++]=f[i++];
        else
        {
            ans+=m-i+1;
            t[cnt++]=f[j++]; //核心代码,求解逆序数个数。
        }
    }
    while(i<=m) //若左表不空
        t[cnt++]=f[i++];
    while(j<=r) //若右表不空
        t[cnt++]=f[j++];
    for(int k=0;k<cnt;) //修改原数组
        f[l++]=t[k++];
}
void Merge_sort(int l,int r) //归并排序
{
    if(l==r)
        return ;
    else
    {
        int m=(l+r)>>1;
        Merge_sort(l,m);
        Merge_sort(m+1,r);
        Merge(l,m,r);
    }
}
int  main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&f[i]);
        ans=0;
        Merge_sort(0,n-1);
        printf("Scenario #%d:\n%d\n\n",++cas,ans);
    }
    return 0;
}

例题2:POJ 2299.    点击打开链接

跟上题没有什么区别,但n较大,O(n^2)的算法必然超时,故必须使用Merge_sort,同时注意要使用 long long 。

#include<cstdio>
#define N 500000+10

long long ans=0;
int f[N],t[N];
void Merge(int l,int m,int r)
{
    int i=l,j=m+1,cnt=0;
    while(i<=m && j<=r)
    {
        if(f[i]<=f[j])
            t[cnt++]=f[i++];
        else
        {
            ans+=m-i+1;
            t[cnt++]=f[j++];
        }
    }
    while(i<=m)
        t[cnt++]=f[i++];
    while(j<=r)
        t[cnt++]=f[j++];
    for(int k=0;k<cnt;)
        f[l++]=t[k++];
}
void Merge_sort(int l,int r)
{
    if(l==r)
        return ;
    else
    {
        int m=(l+r)>>1;
        Merge_sort(l,m);
        Merge_sort(m+1,r);
        Merge(l,m,r);
    }
}
int  main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&f[i]);
        ans=0;
        Merge_sort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}

例题3: hdu 4911.  点击打开链接

这里题目另设条件,只能交换k次,所以,先用Merge_sort求出ans,然后与k进行比较即可(ans<=k  ->0 ;  ans>k  -> ans-k ;)。

#include<cstdio>
#define N 500000+10

long long ans=0;
int f[N],t[N];
void Merge(int l,int m,int r)
{
    int i=l,j=m+1,cnt=0;
    while(i<=m && j<=r)
    {
        if(f[i]<=f[j])
            t[cnt++]=f[i++];
        else
        {
            ans+=m-i+1;
            t[cnt++]=f[j++];
        }
    }
    while(i<=m)
        t[cnt++]=f[i++];
    while(j<=r)
        t[cnt++]=f[j++];
    for(int k=0;k<cnt;)
        f[l++]=t[k++];
}
void Merge_sort(int l,int r)
{
    if(l==r)
        return ;
    else
    {
        int m=(l+r)>>1;
        Merge_sort(l,m);
        Merge_sort(m+1,r);
        Merge(l,m,r);
    }
}
int  main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)==2)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&f[i]);
        ans=0;
        Merge_sort(0,n-1);
        if(ans>k) printf("%lld\n",ans-k);
        else printf("0\n");
    }
    return 0;
}
时间: 03-30

归并排序求逆序数(POJ 1804,POJ 2299,HDU 4911)的相关文章

poj 2299 Ultra-QuickSort 归并排序求逆序数对

题目链接: http://poj.org/problem?id=2299 题目描述: 给一个有n(n<=500000)个数的杂乱序列,问:如果用冒泡排序,把这n个数排成升序,需要交换几次? 解题思路: 根据冒泡排序的特点,我们可知,本题只需要统计每一个数的逆序数(如果有i<j,存在a[i] > a[j],则称a[i]与 a[j]为逆序数对),输出所有的数的逆序数的和用普通排序一定会超时,但是比较快的排序,像快排又无法统计 交换次数,这里就很好地体现了归并排序的优点.典型的利用归并排序求逆

POJ 2299 Ultra-QuickSort (求逆序数:离散化+树状数组或者归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 55048   Accepted: 20256 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

POJ训练计划2299_Ultra-QuickSort(归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 39279   Accepted: 14163 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

poj2299解题报告(归并排序求逆序数)

POJ 2299,题目链接http://poj.org/problem?id=2299 题意: 给出长度为n的序列,每次只能交换相邻的两个元素,问至少要交换几次才使得该序列为递增序列. 思路: 其实就是求逆序数,那么直接向到的就是冒泡了,交换一次,记录一次即可.但是n的范围达到50W,冒泡O(n^2)的复杂度铁定超时. 然后...发现曾经微软有一道笔试题类似就是求逆序数的,对,没错,用归并. 例:合并两个序列(1,3,5)(2,4,6),新序列第二个元素是2,那么它和它前面的3.5形成了逆序数对

HDU 4911 Inversion(归并排序求逆序数)

归并排序求逆序数,然后ans-k与0取一个最大值就可以了. 也可以用树状数组做,比赛的时候可能姿势不对,树状数组wa了.. Inversion Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 578    Accepted Submission(s): 249 Problem Description bobo has a seque

POJ2299 Ultra-QuickSort(归并排序求逆序数)

归并排序求逆序数 Time Limit:7000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent

归并排序求逆序数(排序算法)

归并排序:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并.--(摘自百度百科) 具体操作: 比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,

hiho一下 第三十九周 归并排序求逆序数

题目链接:http://hihocoder.com/contest/hiho39/problem/1 ,归并排序求逆序数. 其实这道题也是可以用树状数组来做的,不过数据都比较大,所以要离散化预处理一下,文中也会给出离散化+树状数组的解法,不过要比归并排序慢一点. 算法: 还是按照题中给的解法. 我们来看一个归并排序的过程: 给定的数组为[2, 4, 5, 3, 1],二分后的数组分别为[2, 4, 5], [1, 3],假设我们已经完成了子过程,现在进行到该数组的“并”操作: a: [2, 4,

poj-2299 Ultra—QuickSort(归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 38688   Accepted: 13950 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin

POJ 2299 Ultra-QuickSort (归并排序求逆序数)

Ultra-QuickSort Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 47235   Accepted: 17258 Description In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swappin