求逆序对的个数-归并排序

原题

题目描述 给定一个整数序列，求逆序对的个数

输入

第一个数为序列长度n，接下来一行，n个整数，保证在int范围内

输出

输出一行，逆序对的个数

输入样例

5 5 4 3 2 1

输出样例 10 数据范围 1<=n<=10^5

思路分析

分治思想 将大数组分成两个小数组，在数组内进行排序和查找逆序对，然后将两个数组合并，递归重复这个过程 求逆序对个数的思想 原来两个小数组内部逆序对的个数加上由于两数组合并而形成的新的逆序对的个数 新形成的逆序对个数的求法 在合并两小数组时，如果左边数组i位置元素小于等于右边数组j位置元素，则把i位置元素放在temp[q]；如果右边j位置小于左边i位置，将j位置元素放在temp[q]，并将count+=leftend-i+1;意思是既然i处元素比j处大，且i处元素原位置在j之前，即i,j处元素构成逆序对，那么i后面到leftend的所有元素都与j处元素构成逆序对。

AC代码

#include<stdio.h> #include<stdlib.h> int data[100010]; int tmp[100010]; void mSort(int k[],int tmp[],int left,int right); long long merge(int k[],int tmp[],int left,int leftend,int rightend); long long num=0; int main() { int i,n; long long count=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&data[i]); mSort(data,tmp,0,n-1); printf("%lld",num); } //分治函数 void mSort(int k[],int tmp[],int left,int right) { int center; long long n; if(left<right) { center=(left+right)/2; mSort(k,tmp,left,center); mSort(k,tmp,center+1,right); n=merge(k,tmp,left,center,right); num+=n; } } //合并函数 long long merge(int k[],int tmp[],int left,int leftend,int rightend) { long long i=left,j=leftend+1,q=left; long long count=0; while(i<=leftend&&j<=rightend) { if(k[i]<=k[j]) tmp[q++]=k[i++]; else { count+=leftend-i+1; tmp[q++]=k[j++]; } } while(i<=leftend) tmp[q++]=k[i++]; while(j<=rightend) tmp[q++]=k[j++]; for(i=left;i<=rightend;i++) k[i]=tmp[i]; return count; }

注意： 一开始提交时是0.9分，原来是有一个组数组num溢出了，需要用long long 来存储。 int的范围是-2,147,483,648 ~ 2,147,483,647。做题时一定要注意估计结果范围，以及注意long long类型的输入和输出都要使用%lld。

其他思路

参考大佬代码，使用了数据离散化。 以及树状数组来解决问题。