题意：给出长度为n的序列，每次只能交换相邻的两个元素，问至少要交换几次才使得该序列为递增序列。

我们需要知道：逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数

所以我们需要求数列的逆序数，O（N*N）的算法肯定会超时的，

所有我们寻求较为高效的排序方法，归并排序就是充分利用分治法的而提高效率的排序方法。

归并排序：

#include <cstdio>
#define M  500005
int n , s[M];
long long ans;
void move(int l, int mid, int r)
{
    int len = r-l+1;
    int *a = new int[len+2];
    int li = l, ri = mid+1, i = 1;
    for(; li<=mid&&ri<=r;)
        if(s[li]<=s[ri]) a[i++] = s[li++];
        else
        {
            a[i++] = s[ri++];
            ans+=(mid-l+1-li+l);
        }
    while(li<=mid) a[i++] = s[li++];
    while(ri<=r) a[i++] = s[ri++];
    for(int j = 1; j <= len; ++j)
        s[j+l-1] = a[j];
    delete a;
}
void merge(int l, int r)
{
    if(l>=r) return;
    int mid = l+(r-l)/2;
    merge(l,mid);
    merge(mid+1,r);
    move(l, mid, r);
}
int main ()
{
    while(scanf("%d",&n), n)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%d",&s[i]);
        ans = 0;
        merge(1,n);
        printf("%I64d\n",ans);
    }
    return 0;
}

我们还可以用树状数组来求其逆序数。
树状数组：

如果第一次接触树状数组的，可以看参考

除特别声明，本站所有文章均为原创，如需转载请以超级链接形式注明出处：SmartCat's Blog