【題目鏈接】

ybt 1311：【例2.5】求逆序對
ybt 1237：求排列的逆序數
OpenJudge NOI 2.4 7622:求排列的逆序數
洛谷 P1908 逆序對
ybt 1311，1237 OpenJudge 2.4 7622幾題輸入數據的最大個數為$10^5$
洛谷 P1908 輸入數據的最大個數為$5?10^5$

【題目考點】

1. 歸并排序 求逆序對

【君義精講】排序算法

【解題思路】

如果直接寫兩層循環尋找逆序對，時間復雜度是$O(n^2)$，該題問題規模為$10^5$，會超時。
可以用歸并排序解決逆序對問題

例：某一次歸并排序，兩個數組分別為a1，a2，臨時數組為t，逆序對數量s:
a1:1 6 8 a2:2 3 7 t: s:0
第一步：a1的1進入到臨時數組t中，1和a2中的數字不產生逆序對
a1:6 8 a2:2 3 7 t:1 s:0
第二步：a2的2比a1的6小，2進入t中。2和a1中的所有元素都形成逆序對，逆序對數量增加2
a1:6 8 a2:3 7 t:1 2 s:2
第三步：a2的3比a1的6小，3進入t中。3和a1中的所有元素都形成逆序對，逆序對數量增加2
a1:6 8 a2:7 t:1 2 3 s:4
第四步：a1的6比a2的7小，6進入t中。不產生逆序對
a1:8 a2:7 t:1 2 3 6 s:4
第五步：a2的7比a1的8小，7進入t中。產生逆序對1個
a1:8 a2: t:1 2 3 6 7 s:5
最后把8 填到t中
a1: a2: t:1 2 3 6 7 8 s:5
此次歸并一共找到5個逆序對

總結規律：在合并有序序列時，當a2數組的最小值比a1數組最小值小的時候，逆序對增加的數量為：此時a1數組剩余元素的個數。其他時刻，逆序對不增加。
根據這一原理編寫程序，歸并排序的時間復雜度是$O(nlogn)$，可以解決規模為$10^5$的問題

n個元素，當整個數組是嚴格降序序列時，有最多的逆序對：
第1元素和后面n-1個元素構成n-1個逆序對；
第2元素和后面n-2個元素構成n-2個逆序對；
。。。
第n-1元素和第n元素構成1個逆序對。
共有逆序對：$n?1+n?2+...+1=\frac{n(n?1)}{2}$
當n為$10^5$時，逆序對最多有約為$10^{10}$個，超出了int可以表示的范圍，所以保存逆序對的變量應該設為long long

【題解代碼】

解法1：

ybt 1311，1237 OpenJudge 2.4 7622幾題 數組長度N可以設為100005
洛谷 P1908 數組長度N必須設為500005

#include<bits/stdc++.h> using namespace std; #define N 500005//數組長度 int a[N], t[N]; long long ct;//逆序數 void mergeSort(int l, int r) {if(l >= r)return;int mid = (l + r)/2;mergeSort(l, mid);mergeSort(mid+1, r);int ti = l, li = l, ri = mid+1;//li第一個段數組中的下標 ri第二段數組中的下標 ti臨時數組中的下標while(li <= mid && ri <= r){if(a[li] <= a[ri])t[ti++] = a[li++];else//如果a[ri] < a[li] 此時a[ri]與左側數組剩余的mid-li+1個數字構成逆序對 {ct += mid-li+1;t[ti++] = a[ri++];}}while(li <= mid)t[ti++] = a[li++];while(ri <= r)t[ti++] = a[ri++];for(int i = l; i <= r; ++i)a[i] = t[i]; } int main() {int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];mergeSort(1, n);cout << ct;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1311：【例2.5】求逆序对 | 1237：求排列的逆序数 | OpenJudge NOI 2.4 7622:求排列的逆序数 | 洛谷 P1908 逆序对的全部內容，希望文章能夠幫你解決所遇到的問題。

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