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

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

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

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

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

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

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

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

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

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

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

 

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

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

本文來自CSDN博客，轉(zhuǎn)載請標(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)

就是最樸素的過橋問題，問最少所需時間

2. pku 2573 Bridge

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

3. zju 1579 Bridge 

這里要用long long 真惡

4. hit 2540 Only One Boat

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

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

5. zju 2288 Across the River

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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