题意

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

思路

归并排序求逆序数，好像是一道模板题捏。（结果居然因为数组开小了而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;
}