考慮1,2,…,n (n <= 100000)的排列i1，i2，…，in，如果其中存在j,k，滿足 j < k 且 ij > ik， 那么就稱(ij,ik)是這個(gè)排列的一個(gè)逆序。
一個(gè)排列含有逆序的個(gè)數(shù)稱為這個(gè)排列的逆序數(shù)。例如排列 263451 含有8個(gè) 逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此該排列的逆序數(shù)就是8。
現(xiàn)給定1,2,…,n的一個(gè)排列，求它的逆序數(shù)。

笨辦法：O(n2)

分治O(nlogn)：
1） 將數(shù)組分成兩半，分別求出左半邊的逆序數(shù)和右半邊的逆序數(shù)
2） 再算有多少逆序是由左半邊取一個(gè)數(shù)和右半邊取一個(gè)數(shù)構(gòu)成(要求O(n)實(shí) 現(xiàn)）

由歸并排序改進(jìn)得到，加上計(jì)算逆序的步驟

MergeSortAndCount: 歸并排序并計(jì)算逆序數(shù)

代碼：

#include<iostream>
using namespace std;
#define N 100000 + 5
int n; 
int a[N];
int b[N];
int ans = 0;
void merge(int L, int R) {int mid = (L + R) / 2;int l = L;int r = mid+1;int count = 0;while(l <= mid && r <= R) {if(a[l] < a[r]) {b[count++] = a[r++];    } else {b[count++] = a[l++];ans += R - r + 1;}}while(l <= mid) b[count++] = a[l++];while(r <= R) b[count++] = a[r++];for(int i = L; i <= R; i++) a[i] = b[i-L];
}
void MergeSortAndCount(int L, int R) {if(L < R) {int mid = (L + R) / 2;MergeSortAndCount(L, mid);MergeSortAndCount(mid + 1, R);merge(L, R);}
}
int main() {scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);MergeSortAndCount(0, n-1);printf("%d\n", ans);return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/kindleheart/p/9416210.html

總結(jié)

以上是生活随笔為你收集整理的求排列的逆序数(分治)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。