昨天我們做了清華的預(yù)選賽，沈大、梁老大、肖叉各搞定一道題，險(xiǎn)些跌出60名。我做了B和F，其中F是關(guān)于逆序數(shù)的題目，復(fù)雜度是 nlog2n+mn 最差的復(fù)雜度可能降為O(n^2)。但我提交的結(jié)果不是TLE，而是MLE和RE。真不知道是清華判題系統(tǒng)有問(wèn)題還是我的程序有問(wèn)題。總之，我心有不服啊，所以決定今天花點(diǎn)時(shí)間歸納一下“逆序?qū)?#8221;的題目，給大家寫(xiě)份報(bào)告，提供點(diǎn)資料。 首先，逆序?qū)Γ╥nversion pair）是指在序列{a0,a1,a2...an}中，若ai<aj(i>j)，則(ai,aj)上一對(duì)逆序?qū)Α６嫘驍?shù)（inversion number）顧名思義就是序列中逆序?qū)Φ膫€(gè)數(shù)。例如： 1 2 3是順序，則逆序數(shù)是0；1 3 2中(2,3)滿(mǎn)足逆序?qū)Φ臈l件，所以逆序數(shù)只有1； 3 2 1中(1,2)(1,3)(2,3)滿(mǎn)足逆序?qū)Γ阅嫘蚴?。由定義不能想象，序列n的逆序數(shù)范圍在[0,n*(n-1)/2]，其中順序時(shí)逆序數(shù)為0，完全逆序時(shí)逆序數(shù)是n*(n-1)/2。

目前我知道的求逆序最快的適合ACM/ICPC的算法是歸并排序時(shí)計(jì)算逆序個(gè)數(shù)，時(shí)間復(fù)雜度是nlog2n，而空間復(fù)雜度2n。JAVA模板（服務(wù)器是校內(nèi)的）。

歸并求逆序簡(jiǎn)單原理：
歸并排序是分治的思想，具體原理自己去看書(shū)吧。利用歸并求逆序是指在對(duì)子序列 s1和s2在歸并時(shí)，若s1[i]>s2[j]（逆序狀況），則逆序數(shù)加上s1.length-i,因?yàn)閟1中i后面的數(shù)字對(duì)于s2[j]都是逆序的。

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

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

PKU 1804, PKU 2299:
是最簡(jiǎn)單的關(guān)于逆序?qū)Φ念}目，題目大意是給出一個(gè)序列，求最少移動(dòng)多少步可能使它順序，規(guī)定只能相鄰移動(dòng)。
相鄰移動(dòng)的話，假設(shè)a b 相鄰，若a<b 交換會(huì)增加逆序數(shù)，所以最好不要做此交換；若a==b 交換無(wú)意思，也不要進(jìn)行此交換；a>b時(shí)，交換會(huì)減少逆序，使序列更順序，所以做交換。
由上可知，所謂的移動(dòng)只有一種情況，即a>b，且一次移動(dòng)的結(jié)果是逆序減1。假設(shè)初始逆序是n，每次移動(dòng)減1，那么就需要n次移動(dòng)時(shí)序列變?yōu)轫樞颉Ｋ灶}目轉(zhuǎn)化為直接求序列的逆序便可以了。

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

PKU 2086:
這題不是求逆序?qū)Γ侵滥嫘驍?shù)k來(lái)制造一個(gè)序列。要求序列最小，兩個(gè)序列比較大小是自左向右依次比較項(xiàng)，擁有較大項(xiàng)的序列大。
其實(shí)造序列并不難，由1804可知，只要對(duì)相鄰數(shù)做調(diào)整就能做到某個(gè)逆序數(shù)了。難點(diǎn)是在求最小的序列。舉例 1 2 3 4 5,要求逆序1的最小序列是交換4 5，如果交換其他任意相鄰數(shù)都無(wú)法保證最小。由此可以想到，要保證序列最小，前部分序列可以不動(dòng)（因?yàn)樗麄円呀?jīng)是最小的了），只改動(dòng)后半部分。而我們知道n個(gè)數(shù)的最大逆序數(shù)是n*(n-1)/2，所以可以求一個(gè)最小的p，使得 k<p*(p-1)/2。得到前半部分是1到n-p，所有的逆序都是由后半部分p個(gè)數(shù)完成的。
考慮k=7,n=6的情況，求得p=5,即前部分1不動(dòng)，后面5個(gè)數(shù)字調(diào)整。4個(gè)數(shù)的最大逆序是5 4 3 2,逆序數(shù)是6，5個(gè)數(shù)是6 5 4 3 2,逆序數(shù)是10。可以猜想到，保證5中4個(gè)數(shù)的逆序不動(dòng)，調(diào)整另一個(gè)數(shù)的位置就可以增加或減少逆序數(shù)，這樣就能調(diào)整出6-10間的任意逆序。為了保證最小，我們可以取盡量小的數(shù)前移到最左的位置就行了。2前移后逆序調(diào)整4，3前移后調(diào)整了3，4調(diào)整2，5調(diào)整1，不動(dòng)是調(diào)整0，可以通過(guò)這樣調(diào)整得到出6-10，所以規(guī)律就是找到需要調(diào)整的數(shù)，剩下的部分就逆序輸出。需要調(diào)整的數(shù)可以通過(guò)總逆序k-(p-1)*(p-2)/2+(n-p)求得。

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

PKU 2893:
用到了求逆序數(shù)的思想，但針對(duì)題目還有優(yōu)化，可見(jiàn)M*N PUZZLE的優(yōu)化。

PKU 1077:
比較經(jīng)典的搜索題，但在判斷無(wú)解的情況下，逆序數(shù)幫了大忙，可見(jiàn)八數(shù)碼實(shí)驗(yàn)報(bào)告。

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/ray58750034/archive/2006/10/08/1325939.aspx