Two Professors
CERC 2008

題目大意:給n條線段,要求劃分成盡可能少的子集,使得在同一個(gè)子集中的線段兩兩不重疊.
同時(shí)限定線段1和線段2不能在同一子集中.

記每條線段為[Li,Ri], 每個(gè)子集的最右端為Bi.
記線段1和2中,L較小的那個(gè)為X,另一個(gè)為Y.

如果沒有那個(gè)限定,容易想到貪心的方法:將所有線段按L從小到大排序.然后依次處理線段k,如果當(dāng)前存在某個(gè)集合的Bi<=Lk,就將Lk加入此集合中,并更新Bi=Rk.否則新開一個(gè)集合放入k.模擬這個(gè)過程,最后的集合數(shù)就是答案.用堆維護(hù)已有集合的信息,時(shí)間復(fù)雜度是O(nlgn).

有了限制條件后,原方法不適用了,因?yàn)樵赬與Y之間處理的線段,對Y有后效性.這會(huì)使得單純按照剛才的方法隨意貪心,可能輪到Y(jié)時(shí),只有X所在集合的Bi<=LY,迫使必須開新集合.但實(shí)際上,有可能可以通過調(diào)整X與Y之間的線段排列結(jié)構(gòu),使Y避開X.
問題關(guān)鍵就是如何判斷能否調(diào)整(并不用關(guān)心詳細(xì)的調(diào)整步驟).
當(dāng)一條線段(P)面臨多個(gè)可插入的集合時(shí),之前的方法是隨意選一個(gè),而不合適的決策正在此產(chǎn)生.下面構(gòu)造一個(gè)情景:
假設(shè)P可以在兩個(gè)集合s,t中選擇,而X在s中.
現(xiàn)在P選擇加入t.
接下來按部就班地處理.
輪到Y(jié)選時(shí),它只能選擇加入s,或者開新的集合.
這時(shí)候,我們能得知,如果當(dāng)初P選擇的是s,緊隨其后的其它選擇也相應(yīng)地對調(diào),那么Y此時(shí)肯定面臨的是只能加入t,或者開新的集合.
這樣Y當(dāng)然直接加入t就行了.
這說明,只要存在一個(gè)這樣的P,當(dāng)Y遭遇X時(shí),肯定存在形狀對稱的另一個(gè)局面使Y避開X,而P就是關(guān)鍵先生.

所以只需稍微改造之前的算法,在處理X與Y之間的線段時(shí),判斷并記錄下是否出現(xiàn)過可選局面.這樣就能正確處理Y遭遇X的情形了.
其它情形時(shí)策略不變(可以證明這樣的解是最優(yōu)的).

代碼略...