POJ2299: Ultra-QuickSort-合并排序解决逆序数问题

时间:2021-07-23 07:44:34
 #include<iostream>
#include<malloc.h>
using namespace std;
long long ans;
void merge(int *a,int le,int mid,int rt){
int *sort_data=(int *)malloc(sizeof(int)*(rt-le+));
if(!sort_data) return;
int i=le,j=mid+,pt=;
while(i<=mid&&j<=rt){
if(a[i]<=a[j]){
sort_data[pt++]=a[i++];
}
else{//exist swap action
sort_data[pt++]=a[j++];
/*
once we swap the postion of both the a[i] and a[j],
we do change the positon of a[i+1......mid]
so as a result, we do change the postion of a[i,i+1,....mid].
*/
ans+=mid-i+;
}
}
while(i<=mid){
sort_data[pt++]=a[i++];
}
while(j<=rt){
sort_data[pt++]=a[j++];
}
int p;
for(int i=le,p=;i<=rt;i++,p++){
a[i]=sort_data[p];
}
}
void mergeSort(int a[],int st,int ed){
if(st<ed){
int mid=(st+ed)/;
mergeSort(a,st,mid);
mergeSort(a,mid+,ed);
merge(a,st,mid,ed);
}
}
int main(){
int n,num[];
while(scanf("%d",&n),n){
ans=;
for(int i=;i<n;i++){
scanf("%d",&num[i]);
}
mergeSort(num,,n-);
printf("%I64d\n",ans);
}
return ;
}