51Nod－1019－逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
Input
第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
Output
输出逆序数
Input示例
4
2
4
3
1
Output示例
4

对于这道题，直接上来的思路就是进行选择对比（类似于选择排序，只不过忽略排序过程），但是只过了七成的数据，所以是不怎么好的，于是乎，了解到，可以用归并排序来做这道题，说到归并排序，最常用的就是用递归来实现，但是其中涉及到一个不断开数组的过程，很有可能会导致题爆掉，所以也是存在很大问题的，所以，想要实现这道题，初步判定需要归并排序，但是要使用非递归实现归并排序，也就是迭代实现。先上递归实现的代码（C）：

#include <stdio.h>
#define _MAX 50001
long ans = 0;

//将有序的A[first..mid]和A[mid + 1..last]归并为有序的B[first..last]
void Merge(long *A, long *B, int first, int mid, int last)
{
    int i = first, j = mid + 1;
    int cur = first;
    while (i <= mid && j <= last)
    {
        if (A[i] <= A[j])
        {
            B[cur++] = A[i++];
        }
        else
        {
            B[cur++] = A[j++];
            ans += mid - i + 1; //核心代码，逆序数增加
        }
    }
    while (i <= mid)
    {
        B[cur++] = A[i++];
    }
    while (j <= last)
    {
        B[cur++] = A[j++];
    }
}

//将A[first..last]归并排序为B[first..last]
void MSort(long *A, long *B, int first, int last)
{
    int mid;
    long BT[_MAX];  //这里存在问题，当数据大时，递归层数多，容易爆掉。
    if (first == last)
    {
        B[first] = A[first];
    }
    else
    {
        mid = (first + last) / 2;
        MSort(A, BT, first, mid);
        MSort(A, BT, mid + 1, last);
        Merge(BT, B, first, mid, last);
    }
    return ;
}

int main(int argc, const char * argv[])
{
    int N, i = 1;
    long A[_MAX];
    scanf("%d", &N);
    for (; i <= N; i++)
    {
        scanf("%ld", &A[i]);
    }

    MSort(A, A, 1, N);

    printf("%ld\n", ans);
    return 0;
}

这个代码只过了七成的测试数据，不是完美的解题代码，所以接下来要给出真正可行的代码，如下（C）：

#include <stdio.h>
#include <stdlib.h>
#define _MAX 50001
long ans = 0;

//将有序的A[first..mid]和A[mid + 1..last]归并为有序的B[first..last]
void Merge(long *A, long *B, int first, int mid, int last)
{
    int i = first, j = mid + 1;
    int cur = first;
    while (i <= mid && j <= last)
    {
        if (A[i] <= A[j])
        {
            B[cur++] = A[i++];
        }
        else
        {
            B[cur++] = A[j++];
            ans += mid - i + 1; //核心代码，逆序数增加
        }
    }
    while (i <= mid)
    {
        B[cur++] = A[i++];
    }
    while (j <= last)
    {
        B[cur++] = A[j++];
    }
}

//将A中相邻长度为s的子序列两两归并到B中
void MergePass(long *A, long *B, int k, int N)
{
    int i = 1, j;
    while (i <= N - 2 * k + 1)
    {
        Merge(A, B, i, i + k - 1, i + 2 * k - 1);
        i = i + 2 * k;
    }
    if (i < N - k + 1)
    {
        Merge(A, B, i, i + k - 1, N);
    }
    else
    {
        for (j = i; j <= N; j++)
        {
            B[j] = A[j];
        }
    }
}

void MSort(long *A, int N)
{
    long *B = (long *)malloc(sizeof(long) * N);
    int k = 1;
    while (k < N)
    {
        MergePass(A, B, k, N);
        k *= 2;
        MergePass(B, A, k, N);
        k *= 2;
    }
    return ;
}

int main(int argc, const char * argv[])
{
    int N, i = 1;
    long A[_MAX];
    scanf("%d", &N);
    for (; i <= N; i++)
    {
        scanf("%ld", &A[i]);
    }

    MSort(A, N);

    printf("%ld\n", ans);
    return 0;
}

理论上这种写法是可以AC的，但是不知道为啥，在三组测试数据中出现了运行时错误，一下子整个人都不自在了，25组测试数据，大的过去了，小的也过去了，偏偏是这中不溜的三组数据出现了问题，自己本地测试数据，结果均正确，搞得我不知所以了……

51Nod－1019－逆序数

全站热榜