[数据结构与算法]【树形结构】训练题N - Ultra-QuickSort

题意

给一个无序的数组，只能交换相邻两个数，变换成从小到大的数列，问最少需要多少次

思路

归并排序求逆序数，好像是一道模板题捏。（结果居然因为数组开小了而RE了一次）

代码

#include<iostream>
#include<cmath>
#include<stack>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>

#define Endl "\n"
typedef long long ll;
const int maxn=1e6+5;
const int mod=1e9+7;
using namespace std;
ll sum,t;
int num[maxn];
int tmp[maxn];
void merge(int low, int mid, int high)
{
    int i,j,k;
    i=k=low;
    j=mid+1;
    while(i<=mid && j<=high)
    {
        if(num[i]<num[j])
            tmp[k++]=num[i++];
        else
        {
        	sum+=j-k;
            tmp[k++]=num[j++];
        }
    }
    while(i<=mid)
        tmp[k++]=num[i++];
    while(j<=high)
        tmp[k++]=num[j++];
    for(i=low; i<=high; ++i)
        num[i]=tmp[i];
    return ;
}
 
void mergeSort(int a, int b)
{
    int mid;
    if(a<b)
    {
        mid=(a+b)/2;
        mergeSort(a, mid);
        mergeSort(mid+1, b);
        merge(a, mid, b);
    }
    return ;
}
inline ll read()
{
	ll x = 0, f = 1; char ch; ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{

	while(t=read())
	{
		if(t!=0)
		{
		
		sum=0;
		for(int i=1;i<=t;i++)
			num[i]=read();
		mergeSort(1,t);
		printf("%lld\n",sum);
		}
	}
	return 0;
}