学步园

//求逆序数对<br /> #include<iostream><br /> using namespace std;<br /> const int MAXN = 500001;<br /> long long int A[MAXN],T[MAXN],cnt;<br /> void merge_sort(long long int *A,int x,int y,long long int *T,long long int &cnt)//归并排序<br /> {<br /> if(y-x > 1)<br /> {<br /> int m = x + (y-x)/2;//划分过程<br /> int p = x,q = m,i = x;<br /> merge_sort(A,x,m,T,cnt);//递归求解[x,m)<br /> merge_sort(A,m,y,T,cnt);//递归求解[m,y)<br /> while(p < m || q < y)//合并过程，条件为：只要有一个序列非空，就继续合并<br /> {<br /> if(q >= y || (p < m && A[p] <= A[q]))//第二个序列为空或者第二个序列非空且A[p] <= A[q]，则复制A[p]<br /> T[i++] = A[p++];//复制左半数组<br /> else<br /> {<br /> T[i++] = A[q++];//复制又半数组<br /> cnt += m-p;//加上左边数组元素个数，由于归并排序是从小到大运行，所以左边没来得及复制的元素个数即为逆序数<br /> }<br /> }<br /> for(int i = x;i < y;++i)//从辅助空间复制回A数组<br /> A[i] = T[i];<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> while(cin >> n)<br /> {<br /> cnt = 0;<br /> if(n == 0)break;<br /> for(int i = 0;i < n;++i)<br /> cin >> A[i];<br /> merge_sort(A,0,n,T,cnt);<br /> cout << cnt << endl;<br /> }<br /> return 0;<br /> }