- 题目描述：
- 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
- 输入：
-
每个测试案例包括两行：第一行包含一个整数n，表示数组中的元素个数。其中1 <= n <= 10^5。第二行包含n个整数，每个数组均为int类型。
- 输出：
- 对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。
样例输入：
4 7 5 6 4
样例输出：
5
【解题思路】本题还是有一定的难度的，首先我们不可能通过遍历的方案来完成，时间复杂度过高。然后我们可以想象，是否我们可以通过分块完成，完成字块的统计后，我们使字块有序，然后继续统计其他字块。最后我们合并统计字块。我们融入一种合并排序的思想，通过小块的统计并有序来构造更大的有序块，直到最后全部合并完成。对于两个有序小块之间包含的逆序对，我们只需要判断有限的组合即可完成统计。
AC code：
#include <cstdio> #include <vector> using namespace std; int aa[50005],bb[50005]; long long merge(int num[],const int&a,const int &b) { if(b-a==1) return 0; long long mid=((a+b)>>1),re=0; re+=merge(num,a,mid); re+=merge(num,mid,b); int acnt=0,bcnt=0; for(int i=a;i<mid;++i) aa[acnt++]=num[i]; for(int i=mid;i<b;++i) bb[bcnt++]=num[i]; int numidx=a,aidx=0,bidx=0; while(aidx<acnt && bidx<bcnt) { if(aa[aidx]>bb[bidx]) { re+=bcnt-bidx; num[numidx++]=aa[aidx++]; }else num[numidx++]=bb[bidx++]; } while(aidx<acnt) num[numidx++]=aa[aidx++]; while(bidx<bcnt) num[numidx++]=bb[bidx++]; return re; } int main() { int n; while(scanf("%d",&n)!=EOF) { long long cnt=0; int num[100002]; for(int i=0;i<n;++i) { scanf("%d",&num[i]); } cnt=merge(num,0,n); printf("%lld ",cnt); } return 0; } /************************************************************** Problem: 1348 User: huo_yao Language: C++ Result: Accepted Time:100 ms Memory:1732 kb ****************************************************************/题目链接：http://ac.jobdu.com/problem.php?pid=1348九度-剑指Offer习题全套答案下载：http://download.csdn.net/detail/huoyaotl123/8276299