Time Limit: 1 SecMemory Limit: 128 MB
Submit: 642Solved: 147
Description
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数不小于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
Input
多组测试数据
每组测试数据分两行，第一行一个正整数n（n <= 50000)
第二行有n个元素(0 <= A[i] <= 10^9)
Output
每组测试数据输出一行表示逆序数
Sample Input
4
2 4 3 1
3
1 1 1
Sample Output
4
3
归并排序复习：[算法]——归并排序（Merge Sort） - eudiwffe - 博客园
数据结构及算法基础--归并排序（Merge Sort） - 霄十一郎 - 博客园
思路：分别对前面和后面进行归并排序，然后合并起来
代码参考：【ZCMU1203】逆序数（归并） - よろしくお願いします - CSDN博客
zcmu--1203: 逆序数（归并排序） - 冲鸭٩꒰▽ ꒱۶⁼³₌₃ - CSDN博客
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn],sum;
void mergeSort(int front,int mid,int rear)//归并排序-合并部分
{
int x1=front,x2=mid+1,count=0;
while(x1<=mid && x2<=rear){
if(a[x1]<a[x2])
b[count++]=a[x1++] ;
else {
sum+=(mid-x1+1);
b[count++]=a[x2++];
}
}
while(x1<=mid)
b[count++] = a[x1++];
while(x2<=rear)
b[count++] = a[x2++];
for(int i=front;i<=rear;i++)
a[i]=b[i-front]; //
}
void merge(int front,int rear){
if(front<rear){
int mid=(front+rear)/2;//二分循环
merge(front,mid); //前部分排序
merge(mid+1,rear);//后部分排序
mergeSort(front,mid,rear);//合并前后两部分呢
}
}
int main()
{
int n,i,j,count;
while(~scanf("%d",&n)){
sum=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
merge(0,n-1);
printf("%d\n",sum);
}
return 0;
}
