版权声明：本文为博主原创文章，未经博主同意不得转载。

https://blog.csdn.net/u013912596/article/details/35655703

题目链接：http://poj.org/problem?id=2299

题目大意：求出排序过程中的最小交换次数

利用归并排序的分治算法解决此题。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#define N 500001

using namespace std;

int a[N];

int temp[N];

long long ans;

void merge(int *a,int start,int mid,int end,int *temp)

{

    int ai=start;

    int bi=mid+1;

    int k=0;

    while (ai<=mid&&bi<=end)

    {

        if(a[ai]<=a[bi])

            temp[k++]=a[ai++];

        else

        {

            temp[k++]=a[bi++];

            ans+=(mid-ai+1);

        }

    }

    while (ai<=mid)

        temp[k++]=a[ai++];

    while (bi<=end)

        temp[k++]=a[bi++];

    for(int i=0;i<=end-start;i++)

    {

        a[start+i]=temp[i];

    }

}

void merge_array(int *a,int start,int end)

{

    if(start<end)

    {

        int mid=(start+end)/2;

        merge_array(a,start,mid);

        merge_array(a,mid+1,end);

        merge(a,start,mid,end,temp);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    while(n)

    {

        memset(a,0,sizeof(a));

        ans=0;

        for(int i=0;i<n;i++)

            scanf("%d",&a[i]);

        merge_array(a,0,n-1);

        printf("%I64d\n",ans);

        scanf("%d",&n);

    }

    return 0;

}