POJ：2299-Ultra-QuickSort（归并排序，求逆序数）

归并排序

• 题面链接

• 题意

  输入一个n,接下来输入n个数，求这n个数转换成从小到大顺序，最少要经过多少次相邻数字的交换

• 样例

  Sample Input
  5
  9
  1
  0
  5
  4
  3
  1
  2
  3
  0
  Sample Output
  6
  0

• 分析（摘自博客）

  两个数（a, b）的排列，若满足a > b，则称之为一个逆序对。
  很明显可以知道，如果相邻的两个元素满足前一个大于后一个，则肯定要交换一次，因为最终位置是小的在前，大的在后。因此本题其实就是求原数组中的逆序对的数目。
  求逆序对的数目可以使用归并排序，其实逆序对的数目是归并排序的一个附属产品，只是在归并排序的过程中顺便算出来的。
  （2路）归并排序的思想：先把每个数看成一段，然后两两合并成一个较大的有序数组，再把较大的两两合并，直到最后成为一个有序数组。
  例如：
  初始数组为：4 2 1 3
  先把每个数看成一段，即：4 ｜ 2 ｜ 1 ｜ 3
  接着两两合并成有序数组，即：2 4 ｜ 1 3
  最后合并成总的有序数组，即：1 2 3 4
  不难发现，在排序过程中，若某个数向前移动了N位，则必定存在N个逆序数。比如上面第二轮排序中，数字1一开始是在第2位，后面移到了第0位，前进了两位，因此必定存在两个逆序，即（2, 1）， （4, 1）。所以只需要在归并排序过程中把这个数记录下来即可得到结果。

• 代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long num[500005];
long long temp[500005];
long long ans;
void merge(int l,int mid,int r)
{
    int i=l;
    int j=mid+1;
    int k=l;
    while(i<=mid&&j<=r)
    {
        if(num[i]<=num[j])
            temp[k++]=num[i++];
        else
        {
            ans+=j-k;
            temp[k++]=num[j++];
        }
    }
    while(i<=mid)
        temp[k++]=num[i++];
    while(j<=r)
        temp[k++]=num[j++];
    for(i=l;i<=r;i++)
        num[i]=temp[i];
}
void mergesort(int a,int b)
{
    if(a<b)
    {
        int mid=(a+b)/2;
        mergesort(a,mid);
        mergesort(mid+1,b);
        merge(a,mid,b);
    }
}
int main()
{
    long long n,i;
    while(scanf("%lld",&n),n)
    {
        ans=0;
        for(int i=0;i<n;i++)
            scanf("%lld",&num[i]);
        mergesort(0,n-1);
        printf("%lld\n",ans);
    }
    return 0;
}