關于問題
描述
在Internet上的搜索引擎經常需要對信息進行比較，比如可以通過某個人對一些事物的排名來估計他（或她）對各種不同信息的興趣，從而實現個性化的服務。
對于不同的排名結果可以用逆序來評價它們之間的差異。考慮1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，滿足 j < k 且 ij > ik， 那么就稱(ij,ik)是這個排列的一個逆序。
一個排列含有逆序的個數稱為這個排列的逆序數。例如排列 263451 含有8個逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此該排列的逆序數就是8。顯然，由1,2,…,n 構成的所有n!個排列中，最小的逆序數是0，對應的排列就是1,2,…,n；最大的逆序數是n(n-1)/2，對應的排列就是n,(n-1),…,2,1。逆序數越大的排列與原始排列的差異度就越大。
現給定1,2,…,n的一個排列，求它的逆序數。
輸入
第一行是一個整數n，表示該排列有n個數（n <= 100000)。 第二行是n個不同的正整數，之間以空格隔開，表示該排列。
輸出
輸出該排列的逆序數。
樣例輸入
6 2 6 3 4 5 1
樣例輸出
8
解決方法
思路：
采用分治的思想 （1）將數組分成兩半，分別求出左半邊的逆序數計和右半邊的逆序數 （2）再計算有多少逆序是左半邊取一個數和右半邊取一個數所構成的 （3）整個部分的逆序數等于三者之和
重點：
如何在O(n)時間內實現（2） 關鍵：我們要求左半邊和右半邊都是排好序的，比如都是從大到小排序，這樣，左右半邊只需要從頭到尾各掃描一遍，便可實現（2）
注意：
結果可能超過int的范圍，需要用long long存儲。
代碼
#include<iostream>#include<cstdio>using namespace std;int a[100005];int b[100005]; long long Count(int a[],int s,int m,int e){ long long num = 0; int i = s,j = m+1; while(i <= m && j <= e) { if(a[i] <= a[j]) ++j; else { num += e-j+1; ++i; } } return num;} void Merge(int a[],int s,int m,int e,int tmp[]){ int pb = 0; int p1 = s,p2 = m+1; while( p1 <= m && p2 <= e) { if(a[p1] > a[p2]) //從大到小 tmp[pb++] = a[p1++]; else tmp[pb++] = a[p2++]; } while( p1 <= m) tmp[pb++] = a[p1++]; while( p2 <= e) tmp[pb++] = a[p2++]; for(int i = 0;i < e-s+1; ++i) a[s+i] = tmp[i]; }long long MergeSortandCount(int a[],int s,int e,int tmp[]){ if(s < e) { int m = s+(e-s)/2; long long left = MergeSortandCount(a,s,m,tmp); long long right = MergeSortandCount(a,m+1,e,tmp); long long landr = Count(a,s,m,e); Merge(a,s,m,e,tmp); return left + right + landr; } return 0;}int main(){ int size; scanf("%d",&size); for(int i=0;i < size;i++) scanf("%d",&a[i]);
