昨天我們做了清華的預(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)滿足逆序?qū)Φ臈l件，所以逆序數(shù)只有1； 3 2 1中(1,2)(1,3)(2,3)滿足逆序?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

//

//

1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)

就是最樸素的過(guò)橋問(wèn)題，問(wèn)最少所需時(shí)間

2. pku 2573 Bridge

在1的基礎(chǔ)上加上過(guò)橋所需要的步驟

3. zju 1579 Bridge 

這里要用long long 真惡

4. hit 2540 Only One Boat

這個(gè)題目是過(guò)橋問(wèn)題的變種,題目的意思就是有N隊(duì)夫妻,現(xiàn)在要過(guò)河，但是只有一條船，并且船每次只能載兩個(gè)人。要求每一個(gè)妻子不能在丈夫不在的情況下與其他男人在一起，無(wú)論是船上還是岸上都不可以。問(wèn)最少的次數(shù)使得所有人過(guò)河，并打印具體的步驟(spj)。

這個(gè)問(wèn)題最少次數(shù)其實(shí)是固定的，不難推出如果有n隊(duì)夫妻，那么全部過(guò)河的最少次數(shù)是5*n-3。（這個(gè)原因我請(qǐng)教了這個(gè)題目的作者，他的意思是最優(yōu)的策略一定是兩個(gè)人坐船去彼岸，一個(gè)人坐船回此岸。因此最少次數(shù)是一定的)。知道了最少次數(shù)如何去打印具體步驟了，其實(shí)我們從樣例中3隊(duì)夫妻的說(shuō)明中可以得到一些啟發(fā)，就是說(shuō)經(jīng)過(guò)若干步之后可以使得一對(duì)夫妻"Leave"。 例如3隊(duì)夫妻的時(shí)候，標(biāo)號(hào)為1，2為第一對(duì)夫妻（奇數(shù)為男，偶數(shù)為女，下同）,標(biāo)號(hào)為3，4為第二對(duì)夫妻，標(biāo)號(hào)為5，6為第三對(duì)夫妻。那么由2，4首先坐船來(lái)到彼岸，然后2回去，2和6再來(lái)到彼岸回去，然后6回去，讓1，3過(guò)來(lái)，然后1和2離開(kāi)，3回頭，3和5再過(guò)去，3和4離開(kāi)，5回頭，5和6過(guò)河并離開(kāi)。 現(xiàn)在轉(zhuǎn)換到n個(gè)人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情況針對(duì)n>=3的情況，我們可以先讓2n和2n-2過(guò)河，然后2n回來(lái)。(注：這個(gè)時(shí)候所形成的局面是此岸有n-1對(duì)夫妻和一個(gè)丈夫，彼岸有一個(gè)該丈夫的妻子）。下面2n和2n-4過(guò)河，然后2n-4回來(lái)，2n-1和2n-3過(guò)河，2n和2n-1 離開(kāi)，2n-3返回。（注：這個(gè)時(shí)候的局面是此案有n-2對(duì)夫妻和一個(gè)丈夫，彼岸有一個(gè)該丈夫的妻子）。可以看出這是一個(gè)遞歸的過(guò)程。下面實(shí)現(xiàn)就簡(jiǎn)單了。

5. zju 2288 Across the River

題目大意: n個(gè)男生和m個(gè)女生過(guò)河.只有一只船,船每次最多裝k人且滿足如下條件:

任何時(shí)候岸邊(包括此岸和彼岸)和船上要么沒(méi)女生.否則女生不比男生少，問(wèn)最少要渡幾次才能使得所有人渡河完畢。

這個(gè)題目如果沒(méi)有說(shuō)要求彼岸也滿足這個(gè)要求（即女生不比男生少，或者沒(méi)有女生），我們可以利用貪心算法解決。

可以總是先把男生給送到彼岸，然后剩下來(lái)的部分都是盡量在滿足條件的情況下把男生往船上放，然后每次把船從彼岸送回來(lái)的人最好是女生。這樣可以使得結(jié)果次數(shù)最少。

但是現(xiàn)在要求的是此案和彼岸都必須滿足條件，這樣的話我們就只能bfs搜了。數(shù)據(jù)量不算大。

結(jié)論一：？哪去了？

結(jié)論二：
一定有這樣一種最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)只需一個(gè)人。　　如果最佳方案中有一步中需要兩個(gè)人從彼岸移動(dòng)到此岸，那么我們可以把這一步改為只移動(dòng)比較快的那個(gè)人。

結(jié)論三：
一定有這樣一種符合結(jié)論二的最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)中，回來(lái)的這個(gè)人一定是當(dāng)時(shí)在彼岸所有人中速度最快的。　

結(jié)論四：
一定有這樣一種符合結(jié)論二—三的最佳方案，在這個(gè)方案里，每當(dāng)出現(xiàn)手電筒在此岸的局面時(shí)，速度最快的那個(gè)人總是在此岸。

結(jié)論五：
一定有這樣一種符合結(jié)論二—四的最佳方案，在這個(gè)方案里，所有從此岸到彼岸的移動(dòng)都需兩個(gè)人。

結(jié)論六：
一定有這樣一種符合結(jié)論二—五的最佳方案，在這個(gè)方案里，每次從此岸到彼岸移動(dòng)兩人，要么這兩人里有一個(gè)是所有人中最快的那個(gè)，要么這兩人到達(dá)彼岸后都再也不回來(lái)。　　　

結(jié)論七：
一定有這樣一種符合結(jié)論二—六的最佳方案，在這個(gè)方案里，所有從彼岸到此岸的移動(dòng)中，回來(lái)的這個(gè)人一定是當(dāng)時(shí)在彼岸所有人中速度最快的，而且他只能是所有人中最快的或者次快的。　
換句話說(shuō)，所有返回此岸的任務(wù)都可以只由跑得最快和跑得次快的人來(lái)?yè)?dān)當(dāng)，所有其他人一旦到達(dá)彼岸，就留在那里，再也不回來(lái)。

結(jié)論八：
一定有這樣一種符合結(jié)論二—七的最佳方案，在這個(gè)方案里，所有除了最快和次快的旅行者都以上面兩個(gè)模式過(guò)橋，并且再不回來(lái)。

假設(shè)A為最快，B為次快，而Z是任意一個(gè)其他旅行者。
模式一:由A護(hù)送到Z對(duì)岸，A返回
模式二:AB->,A<-,YZ->,B<-

結(jié)論九：所有符合結(jié)論八的最佳方案中，最慢兩人過(guò)橋的模式必須相同，而且如果使用的都是模式二，那么他們一定在一起過(guò)河。

結(jié)論　
　如果給定N個(gè)（速度不同）的旅行者，根據(jù)結(jié)論九我們知道有一個(gè)最佳方案，在最初的4步里用模式一或模式二把最慢的兩個(gè)旅行者移動(dòng)到彼岸，于是問(wèn)題被約化成N-2個(gè)旅行者的形式。問(wèn)題在于應(yīng)該選擇哪一種模式。繼續(xù)假設(shè)A、B為走得最快和次快的旅行者，過(guò)橋所需時(shí)間分別為a、b；而Z、Y為走得最慢和次慢的旅行者，過(guò)橋所需時(shí)間分別為z、y。　　
在第六節(jié)中我們發(fā)現(xiàn)
使用模式一移動(dòng)Z和Y到彼岸所需的時(shí)間為：z + a + y + a
使用模式二移動(dòng)Z和Y到彼岸所需的時(shí)間為：b + a + z + b
所以，　　　
當(dāng)2b＞a+y時(shí)，應(yīng)該使用模式一；
當(dāng)2b＜a+y時(shí)，應(yīng)該使用模式二　
當(dāng)2b＝a+y時(shí)，使用模式一或二都可以。　　
上面的討論都是在N≥4時(shí)進(jìn)行的，那時(shí)最快、次快、最慢和次慢是四個(gè)不同的人。所以我們還要稍微討論一下N=1、2、3的情況。　　N=1、2是不用動(dòng)腦子的，直接通通過(guò)橋就是了。　
N=3也很簡(jiǎn)單，用窮舉法可以發(fā)現(xiàn)由最快的人往返一次把其他兩人送過(guò)河是最快的方法。　　
于是我們得到了最終結(jié)論：最佳方案構(gòu)造法：
以下是構(gòu)造N個(gè)人(N≥1)過(guò)橋最佳方案的方法：　　
1) 如果N=1、2，所有人直接過(guò)橋。　　
2) 如果N=3，由最快的人往返一次把其他兩人送過(guò)河。　
3) 如果N≥4，設(shè)A、B為走得最快和次快的旅行者，過(guò)橋所需時(shí)間分別為a、b；而Z、Y為走得最慢和次慢的旅行者，過(guò)橋所需時(shí)間分別為z、y。
那么　　
當(dāng)2b＞a+y時(shí)，使用模式一將Z和Y移動(dòng)過(guò)橋；　　　　
當(dāng)2b＜a+y時(shí)，使用模式二將Z和Y移動(dòng)過(guò)橋；　　　
當(dāng)2b＝a+y時(shí)，使用模式一將Z和Y移動(dòng)過(guò)橋。
這樣就使問(wèn)題轉(zhuǎn)變?yōu)镹-2個(gè)旅行者的情形，從而遞歸解決之。　
　最后當(dāng)然我們要舉一個(gè)具體的例子：七個(gè)旅行者，所需過(guò)橋時(shí)間分別是1、4、5、5、5、8、9分鐘。　　
我們假設(shè)他們順次為A、B、C、D、E、F、G，我們注意到C、D、E的速度一樣，用第二節(jié)的方法太正規(guī)也太麻煩，我們可以人為規(guī)定C速度稍稍大于D，D速度又稍稍大于E。
采用結(jié)論十的方法，最快和次快的是A、B，時(shí)間為1和4；最慢和次慢的是G和F，時(shí)間為9和8。
現(xiàn)在2*4＜1+9，所以用模式二：
第1步：　　　　　　A B →　　4
第2步：　　　　　　　A ←　　1
第3步：　　　　　　F G →　　9
第4步：　　　　　　　B ←　　4
現(xiàn)在剩下A、B、C、D、E在此岸，最快和次快的是A、B，時(shí)間為1和4；最慢和次慢的是E和D，時(shí)間為5和5。
現(xiàn)在2*4＞1+5，所以用模式一：
第5步：　　　　　　A E →　　5
第6步：　　　　　　　A ←　　1
第7步：　　　　　　A D →　　5
第8步：　　　　　　　A ←　　1
現(xiàn)在剩下A、B、C在此岸，用N=3的辦法結(jié)束：
第9步：　　　　　　A C →　　5
第10步：　　　　　　 A ←　　1
第11步：　　　　　 A B →　　4
總的時(shí)間為　　　　4+1+9+4+5+1+5+1+5+1+4 = 40分鐘
雖然我一個(gè)其他的方案都沒(méi)列舉，我知道這個(gè)40分鐘的方案必定是最佳的。

//呵呵 //找規(guī)律，類(lèi)似斐波那契數(shù)列
//每對(duì)頂點(diǎn)之間的最短路徑算法floyd，其實(shí)是動(dòng)歸，O(n³)，還要注意disjoint