AcWing 107. 超快速排序
原题链接
简单
作者:
骄骄是骄傲的骄骄
,
2022-02-25 20:01:15
,
所有人可见
,
阅读 187
/*
归并排序
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=5e5+10;
int arr[N];
LL res=0;
void MergeSort(int l, int r){
if(l>=r) return ;
int mid=l+r>>1;
MergeSort(l, mid), MergeSort(mid+1, r);
int t[N];
int k=0, i=l, j=mid+1;
while(i<=mid && j<=r)
if(arr[i]<=arr[j]) t[k++]=arr[i++];
else t[k++]=arr[j++], res+=mid-i+1;
// 后面序列的数要扔到前面去
// 必定需要越过 i-mid 这些数,而这些数,都是逆序的
// 因此数量为 mid-i+1
while(i<=mid) t[k++]=arr[i++];
while(j<=r) t[k++]=arr[j++];
for(int i=l, j=0; i<=r; ) arr[i++]=t[j++];
}
int main(){
int n=0;
// 长度
while(cin>>n){
if(!n) break;
// 重置数组
memset(arr, 0, sizeof arr);
// 重置答案
res=0;
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);
MergeSort(0, n-1);
cout<<res<<endl;
}
return 0;
}