昨天我們做了清華的預選賽，沈大、梁老大、肖叉各搞定一道題，險些跌出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

//

//

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

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

2. pku 2573 Bridge

在1的基礎上加上過橋所需要的步驟

3. zju 1579 Bridge 

這里要用long long 真惡

4. hit 2540 Only One Boat

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

這個問題最少次數其實是固定的，不難推出如果有n隊夫妻，那么全部過河的最少次數是5*n-3。（這個原因我請教了這個題目的作者，他的意思是最優的策略一定是兩個人坐船去彼岸，一個人坐船回此岸。因此最少次數是一定的)。知道了最少次數如何去打印具體步驟了，其實我們從樣例中3隊夫妻的說明中可以得到一些啟發，就是說經過若干步之后可以使得一對夫妻"Leave"。 例如3隊夫妻的時候，標號為1，2為第一對夫妻（奇數為男，偶數為女，下同）,標號為3，4為第二對夫妻，標號為5，6為第三對夫妻。那么由2，4首先坐船來到彼岸，然后2回去，2和6再來到彼岸回去，然后6回去，讓1，3過來，然后1和2離開，3回頭，3和5再過去，3和4離開，5回頭，5和6過河并離開。 現在轉換到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對夫妻和一個丈夫，彼岸有一個該丈夫的妻子）。可以看出這是一個遞歸的過程。下面實現就簡單了。

5. zju 2288 Across the River

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

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

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

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

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

結論一：？哪去了？

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

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

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

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

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

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

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

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

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

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

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