Two Professors
CERC 2008

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

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

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

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

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

代碼略...