题解 UVA299 【Train Swapping】

· · 个人记录

逆序对模板题，逆序对一般正解是 O(n\log n) 的，但是看到了“入门”你就知道这道题 O(n^2) 是绝对过得了的。

但O(n^2) 的冒泡排序不是重点，我们来讲一讲以后用的到的 O(n \log n) 归并排序。

归并排序运用的是“分而治之”的思想，首先把数组 A 不断分叉（如图），直到每个部分元素个数都为1。

然后我们把这个操作反过来做一遍，把这些部分按照分裂的顺序合并起来。

在合并的过程中，我们要保证每一个部分当前都是有序的，所以我们需要在合并的过程中更改原来的数组，而更改的过程中又需要读取当前合并的两个部分的元素，所以不妨再声明一个临时数组 tmp 。

有了临时数组，我们就可以快乐的合并了，首先我们声明两个指针 i,j ，并把它们分别指向当前合并的左边部分第一个元素 A[l] 和右边部分第一个元素 A[mid+1] （ mid 就是合并后区间的中点，即左区间最后一个元素的位置）。我们不断比较 A[i] 和 A[j] 的大小，直到 i=mid 或 j=r 如果 A[i]>A[j] （注意， i 一定小于 j ，因为 i 在左区间），则说明我们找到了一个逆序对，又因为每个区间都在合并前是已经排好序了的，所以可以保证 A[j] 一定小于左区间下标大于 i 的元素，此时我们把答案加上 mid-i+1 ，并把 A[j] 插入临时数组。若 A[i] \leq a[j]，则直接把 A[i] 插入临时数组。

当 i=mid 或 j=r 时，说明已经有一个区间被选完了，这是直接把另一区间所有元素依次插入临时数组并用临时数组覆盖当前合并的两个区间即可。

以上就是合并与统计的操作，我们不断执行这个操作，不断递归就可以用 O(n \log n) 的时间复杂度求出逆序对数目并且给数组排序了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int n,c[500001],tmp[500001];
long long ans;
void go(int l,int r)
{
    if (l>=r)return;
    int mid=(l+r)>>1;
    go(l,mid);
    go(mid+1,r);
    int i=l,j=mid+1,zz=l;
    while (i<=mid&&j<=r)
    {
        if (c[j]<c[i])
        {
            tmp[zz]=c[j];
            zz++;
            ans+=mid+1-i;
            j++;
        }
        if (c[j]>=c[i])
        {
            tmp[zz]=c[i];
            zz++;
            i++;
        }
    }
    while (i<=mid)
    {
        tmp[zz]=c[i];
        zz++;
        i++;
    }
    while (j<=r)
    {
        tmp[zz]=c[j];
        zz++;
        j++;
    }
    for (i=l;i<=r;i++)c[i]=tmp[i];
}
int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        ans=0;
        cin>>n;
        for (int i=1;i<=n;i++)cin>>c[i];
        go(1,n);
        cout<<"Optimal train swapping takes "<<ans<<" swaps.\n";
    }
}