題目鏈接：http://115.159.40.116/problem_show.php?pid=4729
或者：http://acm.nyist.net/JudgeOnline/problem.php?pid=117

求逆序數

時間限制：2000?ms ?|? 內存限制：65535?KB 難度：5 描述

在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。

現在，給你一個N個元素的序列，請你判斷出它的逆序數是多少。

比如 1 3 2 的逆序數就是1。

輸入

第一行輸入一個整數T表示測試數據的組數（1<=T<=5)
每組測試數據的每一行是一個整數N表示數列中共有N個元素（2〈=N〈=1000000）
隨后的一行共有N個整數Ai(0<=Ai<1000000000)，表示數列中的所有元素。

數據保證在多組測試數據中，多于10萬個數的測試數據最多只有一組。

輸出

輸出該數列的逆序數

樣例輸入

2 2 1 1 3 1 3 2

樣例輸出

0 1

增加兩組測試數據：
6

2 6 3 4 5 1

答案：8

6

4 5 1 2 6 3

答案：7

一開始用的普通方法，就是時間復雜度為n^2的那種，果然，超時。

筆者是利用并歸排序，實現較短時間求出逆序數，代碼如下：
#include <stdio.h> long long count; int b[1000001], temp[1000001]; void Integration(int a, int m, int e) {//將有序的兩部分整合為一個有序序列int be = a, c = m+1, i = 0;while(be <= m && c <= e) {if(b[be] > b[c]) {temp[i++] = b[be++];count+=e-c+1;//統計逆序} else temp[i++] = b[c++];}while(be <= m) temp[i++] = b[be++];while(i--) b[a+i] = temp[i]; } void MergeSortAndCount(int begin, int end) {//將無序序列分為兩小部分if(end <= begin) return;//直到那小部分只有一個數int mid = (end+begin)/2;MergeSortAndCount(begin, mid);MergeSortAndCount(mid+1, end);Integration(begin,mid,end); } int main() {int t, n, i;scanf("%d", &t);while(t--) {count = 0;scanf("%d", &n);for(i = 0; i < n; i++) scanf("%d", &b[i]);MergeSortAndCount(0,n-1);printf("%lld\n", count);}return 0; }

總結

以上是生活随笔為你收集整理的nyoj117求逆序数 并归排序法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。