昨天我們做了清華的預選賽，沈大、梁老大、肖叉各搞定一道題，險些跌出60名。我做了B和F，其中F是關于逆序數的題目，復雜度是 nlog2n+mn 最差的復雜度可能降為O(n^2)。但我提交的結果不是TLE，而是MLE和RE。真不知道是清華判題系統有問題還是我的程序有問題。總之，我心有不服啊，所以決定今天花點時間歸納一下“逆序對”的題目，給大家寫份報告，提供點資料。 首先，逆序對（inversion pair）是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，則(ai,aj)上一對逆序對。而逆序數（inversion number）顧名思義就是序列中逆序對的個數。例如： 1 2 3是順序，則逆序數是0；1 3 2中(2,3)滿足逆序對的條件，所以逆序數只有1； 3 2 1中(1,2)(1,3)(2,3)滿足逆序對，所以逆序是3。由定義不能想象，序列n的逆序數范圍在[0,n*(n-1)/2]，其中順序時逆序數為0，完全逆序時逆序數是n*(n-1)/2。

目前我知道的求逆序最快的適合ACM/ICPC的算法是歸并排序時計算逆序個數，時間復雜度是nlog2n，而空間復雜度2n。JAVA模板（服務器是校內的）。

歸并求逆序簡單原理：
歸并排序是分治的思想，具體原理自己去看書吧。利用歸并求逆序是指在對子序列 s1和s2在歸并時，若s1[i]>s2[j]（逆序狀況），則逆序數加上s1.length-i,因為s1中i后面的數字對于s2[j]都是逆序的。

TJU 2242:
直接上模板，記得m的奇偶要考慮的哦。

PKU 1007:
求逆序數，然后排序輸出就行了。

PKU 1804, PKU 2299:
是最簡單的關于逆序對的題目，題目大意是給出一個序列，求最少移動多少步可能使它順序，規定只能相鄰移動。
相鄰移動的話，假設a b 相鄰，若a<b 交換會增加逆序數，所以最好不要做此交換；若a==b 交換無意思，也不要進行此交換；a>b時，交換會減少逆序，使序列更順序，所以做交換。
由上可知，所謂的移動只有一種情況，即a>b，且一次移動的結果是逆序減1。假設初始逆序是n，每次移動減1，那么就需要n次移動時序列變為順序。所以題目轉化為直接求序列的逆序便可以了。

ZJU 1481:
這題和本次預選賽的F略有相似，不過要簡單得多。題意是給定序列s，然后依次將序列首項移至序列尾，這樣共有n-1次操作便回到了原序列（操作類似于循環左移）。問這n-1次操作和原序列，他們的逆序數最小的一次是多少？
有模板在手，直觀地可以想到是，對于這n次都求逆序數，然后輸出最小的一次就可以了，但這樣做的復雜度有O(n*nlogn),太過復雜。
如果只求初始序列的逆序數的話，只要后面的n-1次操作的逆序數能夠在O(1)的算法下求得，就能保證總體O(nlogn)的復雜度了。事實上，對于每次操作確實可以用O(1)的算法求得逆序數。將序列中ai移到aj的后面，就是ai做j-i次與右鄰的交換，而每次交換有三個結果：逆序+1、逆序-1、逆序不變。由于題目中說明序列中無相同項，所以逆序不變可以忽略。逆序的加減是看ai與aj間（包括aj）的數字大小關系，所以求出ai與aj間大于ai的數字個數和小于ai的數字個數然后取差，就是ai移動到aj后面所導致的逆序值變化了。
依據上面的道理，因為題目有要求ai是移動到最后一個數，而ai又必定是頭項，所以只要計算大于ai的個數和小于ai的個數之差就行了。然后每次對于前一次的逆序數加上這個差，就是經過這次操作后的逆序數值了。

PKU 2086:
這題不是求逆序對，而是知道逆序數k來制造一個序列。要求序列最小，兩個序列比較大小是自左向右依次比較項，擁有較大項的序列大。
其實造序列并不難，由1804可知，只要對相鄰數做調整就能做到某個逆序數了。難點是在求最小的序列。舉例 1 2 3 4 5,要求逆序1的最小序列是交換4 5，如果交換其他任意相鄰數都無法保證最小。由此可以想到，要保證序列最小，前部分序列可以不動（因為他們已經是最小的了），只改動后半部分。而我們知道n個數的最大逆序數是n*(n-1)/2，所以可以求一個最小的p，使得 k<p*(p-1)/2。得到前半部分是1到n-p，所有的逆序都是由后半部分p個數完成的。
考慮k=7,n=6的情況，求得p=5,即前部分1不動，后面5個數字調整。4個數的最大逆序是5 4 3 2,逆序數是6，5個數是6 5 4 3 2,逆序數是10。可以猜想到，保證5中4個數的逆序不動，調整另一個數的位置就可以增加或減少逆序數，這樣就能調整出6-10間的任意逆序。為了保證最小，我們可以取盡量小的數前移到最左的位置就行了。2前移后逆序調整4，3前移后調整了3，4調整2，5調整1，不動是調整0，可以通過這樣調整得到出6-10，所以規律就是找到需要調整的數，剩下的部分就逆序輸出。需要調整的數可以通過總逆序k-(p-1)*(p-2)/2+(n-p)求得。

PKU 1455:
這是一道比較難的關于逆序數推理的題目，題目要求是n人組成一個環，求做相鄰交換的操作最少多少次可以使每個人左右的鄰居互換，即原先左邊的到右邊去，原右邊的去左邊。容易想到的是給n個人編號，從1..n，那么初始態是1..n然后n右邊是1，目標態是n..1，n左邊是1。
初步看上去好象結果就是求下逆序（n*(n-1)/2 ?），但是難點是此題的序列是一個環。在環的情況下，可以減少許多次移動。先從非環的情況思考，原1-n的序列要轉化成n-1的序列，就是做n(n-1)/2次操作。因為是環，所以(k)..1,n..k+1也可以算是目標態。例如：1 2 3 4 5 6的目標可以是 6 5 4 3 2 1,也可以是 4 3 2 1 6 5。所以，問題可以轉化為求形如(k)..1,n..k+1的目標態中k取何值時，逆序數最小。
經過上面的步驟，問題已經和ZJU1481類似的。但其實，還是有規律可循的。對于某k，他的逆序數是左邊的逆序數+右邊的逆序數，也就是(k*(k-1)/2)+((n-k)*(n-k-1)/2) （k>=1 && k<=n）。展開一下，可以求得k等于n/2時逆序數最小為((n*n-n)/2)，現在把k代入進去就可以得到解了。
要注意的是k是整數，n/2不一定是整數，所以公式還有修改的余地，可以通用地改為(n/2)*(n-1)/2。

PKU 2893:
用到了求逆序數的思想，但針對題目還有優化，可見M*N PUZZLE的優化。

PKU 1077:
比較經典的搜索題，但在判斷無解的情況下，逆序數幫了大忙，可見八數碼實驗報告。

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx