【正文】 Problem E 題目大意： 有一塊草坪，長為 l ，寬為 w ，在它的中心線的位置處裝有 ? ?10000?nn 個(gè)點(diǎn)狀的噴水裝置。所以 km? ,又因?yàn)?m 是最優(yōu)解中選出區(qū)間個(gè)數(shù)，所以 km? 。 16 設(shè)該算法 選出了 k 個(gè)區(qū)間，而最優(yōu)解選出了 m 個(gè)區(qū)間。令 1?i ，假定論斷對(duì) 1?i 為真，即 11 ?? ? ii gf ，最優(yōu)解中選的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)為 ig ,設(shè)它的左端點(diǎn)坐標(biāo)為 ib 。 設(shè) if 為該算法所接受的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)， ig 為某最優(yōu)解中第i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)。 有 n 個(gè)區(qū)間，選擇盡量少的區(qū)間，使得這些區(qū)間完全覆蓋某線段 ? ?ts, 。處理第 i 個(gè)區(qū)間時(shí)，它選擇的位置必是 ??ids 所在集合中的最前面的元素，（若最前面的元素是 ??0s 且 ?? Ls ?0 ，則表示該區(qū)間不能被選擇）。 處理每個(gè)區(qū)間時(shí)，若直接模擬，時(shí)間復(fù)雜度是 ? ?NDO ，最好還是做適當(dāng)優(yōu)化。 算法： 將這些區(qū)間按照權(quán)值從大到小排序，順序處理每個(gè)區(qū)間。每個(gè)貸款需要一個(gè)單位時(shí)間處理，銀行在同一時(shí)間內(nèi)最多可以接受 ? ?1000 ?? LL 個(gè)貸款。如果直接模擬該表的所有操作，時(shí)間復(fù)雜度是 ? ?2NO 。將所有區(qū)間按長度 iW 從小到大排序，依次處理。 時(shí)間復(fù)雜度： 用一棵平衡二叉樹維護(hù) ??ig ，則從 ??ig 遞推 ? ?1?ig 的時(shí)間復(fù)雜度為 ? ?NOlog ， 13 所以總時(shí)間復(fù)雜度為：排序 ? ?NNO log + ??ig 的維護(hù) ? ? ? ?NONO log? = ? ?NNO log 。狀態(tài)數(shù)為 ? ?2NO ，狀態(tài)轉(zhuǎn)移時(shí)間為??1O ，故時(shí)間復(fù)雜度為 ? ?2NO 。（證明和原問題的證明方法類似）在這個(gè)結(jié)論的基礎(chǔ)上，可以得出以下兩種算法。 分析： 把每粒綴珠看作一個(gè)長度為 iW 的區(qū)間，這些區(qū)間的位置是可變的。當(dāng)然區(qū)間帶權(quán)時(shí)，要另外考慮。 綜上所述，該算法成功構(gòu)造了一個(gè)最優(yōu)解。設(shè)兩區(qū)間在交換前后的延遲分別為 il 、 1?il 、 il? 、 1??il 。 命題 既沒有逆序、又沒有空閑段的解是最優(yōu)解。 命題 任何一個(gè)既沒有逆序、又沒有空閑段的解有著相同的最大延遲 L 。顯然 1?if 、 2?if 、?、 nf 減小，即1?il 、 2?il 、?、 nl 減小。 證明： 由于該算法所有區(qū)間都順序放置，因此區(qū)間之間不互相重疊。每個(gè)區(qū) 10 間有兩個(gè)已知參數(shù)：長度 it 和最終期限 id ，設(shè) if 為其右端點(diǎn)坐標(biāo)。如果該算法選擇了某區(qū)間 I ，而某最優(yōu)解中沒有選它，顯然最優(yōu)解選擇了一個(gè)與該區(qū)間重疊且右端點(diǎn)坐標(biāo)大于等于它的區(qū)間 I? ，我們用 I 替換 I? ,就構(gòu)成了一個(gè)包含 I 的最優(yōu)解；如果該算法沒有選擇某區(qū)間，顯然最優(yōu)解也不會(huì)選擇該區(qū)間。在算法 2上稍加改動(dòng)即可得出該題的算法。有 ? ?1000001 ?? nn 艘船，已知每條船的到達(dá)時(shí)刻、離開時(shí)刻和它應(yīng)該進(jìn)入的區(qū)域。這樣做的 總時(shí)間復(fù)雜度也是 ? ?? ?ndnO log 。 實(shí)現(xiàn)： 考慮如何 分配資源。根據(jù)命題 ， ? ? ? ?0101 jSjS ii ?? ?? 。 所以有 ? ? ? ?jSjSdj ii ????? ,1 ，證畢。設(shè)第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)為 ??ie 。 該命題可以運(yùn)用數(shù)學(xué)歸納法來證明。用一個(gè)元素個(gè)數(shù)為 d 的有序表 iS （表中元素始終從小到大排序），記錄處理 i 個(gè)區(qū)間后，各個(gè)資源的 最大右端點(diǎn)坐標(biāo) （當(dāng)某個(gè)資源從沒被用過時(shí)，可認(rèn)為值為 ?? ）。 7 算法 2： 計(jì)算 d 。故總 時(shí) 間 復(fù) 雜 度 為 ： d 的計(jì)算 ? ?nnOlog + 排序 ? ?nnOlog + 分配資源? ?dnO log = ? ?? ?ndnO log 。當(dāng)算法在處理區(qū)間2jI時(shí)，區(qū)間1jI所用資源已經(jīng)被排除，所以不會(huì)被分配到同一資源。所以對(duì)于每個(gè) 6 區(qū)間，都至少 有一個(gè)可分配資源。 證明： 設(shè)排序后的 n 個(gè)區(qū)間分別為 1I ,2I ,? ,nI 命題 每個(gè)區(qū)間都能分配到一個(gè)資源。時(shí)間復(fù)雜度為 排序 ? ?nnO log +掃描 ??nO = ? ?nnO log 由此可得出一個(gè)構(gòu)造算法。記錄一個(gè)值 t ，表示當(dāng)前點(diǎn)被包含次數(shù)。 5 設(shè)區(qū)間 1I ,2I ,? ,dI 全部包含某一點(diǎn)，則必須把這些區(qū)間分配到不同資源中，故至少需要 d 個(gè)資 源。這里就不寫算法了。兩個(gè)外顯子能夠互相聯(lián)接必須滿足某個(gè)外顯子的起始位置在另一個(gè)外顯子的結(jié)束位置之后。 綜上所述，算法選出的區(qū)間是最優(yōu)解。 假設(shè) km? ，根據(jù)命題 ，有 kk gf ? 。則最優(yōu)解的第 i 個(gè)可選區(qū)間所組成的集合包含于執(zhí)行該算法時(shí)第 i 個(gè)可選區(qū)間所組成的集合；而當(dāng)算法選擇第 i 個(gè)區(qū)間時(shí)，選的是在可選區(qū)間中右端點(diǎn)坐標(biāo)最小的一個(gè)，所以有 ii gf ? 。 命題 當(dāng) 1?i 時(shí)，該算法所接受的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo) if ≤某最優(yōu)解中的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo) ig 。 算法： 將所有區(qū)間按右端點(diǎn)坐標(biāo)從小到大排序，順序處理每個(gè)區(qū)間。這類問題變化繁多，解法各異，需要用到貪心、動(dòng)態(tài)規(guī) 劃等算法，并可以用一些數(shù)據(jù)結(jié)構(gòu)優(yōu)化算法。 【關(guān)鍵字】 區(qū)間模型 轉(zhuǎn)化 貪心 動(dòng)態(tài)規(guī)劃 優(yōu)化 2 【引言】 在信息學(xué)競賽中，有很多問題最終都能轉(zhuǎn)化為區(qū)間問題：例如從若干個(gè)區(qū)間中選出一些滿足一定條件的區(qū)間、將各個(gè)區(qū)間分配到一些資源中、或者將一些區(qū)間以某種順序放置等。 3 【正文】 數(shù)軸上有 n 個(gè)區(qū)間，選出最多的區(qū)間，使得這些區(qū)間不互相重疊。 設(shè) if 為該算法所接受的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)， ig 為某最優(yōu)解中的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)。令 1?i ，假定論斷對(duì) 1?i 為真，即 11 ?? ? ii gf 。 命題 最優(yōu)解選出的區(qū)間數(shù)量 m =該算法選出的區(qū)間數(shù)量 k 。所以 km? ,又因?yàn)?m 是最優(yōu)解選出區(qū)間個(gè)數(shù)，所以 km? 。 例題 1： Latin America South America 2022 Problem A 題目大意： 基因是由許多外顯子（ exon）組成， 每個(gè)外顯子都有一個(gè)起始位置和一個(gè)結(jié)束位置。則現(xiàn)在的問題和原問題基本相同 ，只是端點(diǎn)上也不能重疊。 定義區(qū)間集合深度 d 為包含任意一點(diǎn)的區(qū)間數(shù)量的最大值，則顯然有： 命題 需要的資源數(shù)至少為 d 。 d 的計(jì)算方法： 將每個(gè)區(qū)間拆成兩個(gè)事件點(diǎn)，按坐標(biāo)從小到大排序， 順序處理每個(gè)區(qū)間 。注意兩個(gè)相同坐標(biāo)不同類型的事件點(diǎn)的位置關(guān)系和區(qū)間是否能在端點(diǎn)處重疊有關(guān)，這在排序過程中應(yīng)該注意。處理某個(gè)區(qū)間 時(shí)，排除 在它前面且與之重疊的區(qū)間所用到的資源，然后在1,2,3,? ,d 這些資源中任意分配一個(gè)未被排除的資源。故有1??dt ，從而在 d 個(gè)資源中至少有一個(gè)資源沒被這 t 個(gè)區(qū)間排除。 考慮任意兩個(gè)互相重疊的區(qū)間1jI、2jI，其中 21 jj? 。 用二叉堆實(shí)現(xiàn)該優(yōu)先隊(duì)列，每次查找最小值的時(shí)間復(fù)雜度為 ??1O ，修改關(guān)鍵字的時(shí)間復(fù)雜度為 ? ?dOlog ， 分配資源操作的時(shí)間復(fù)雜度也就降為 ? ?dnO log 。 基于這個(gè)命題，我們很容易想到另外一種算法。 證明： 顯然每個(gè)資 源上的區(qū)間都不互相重疊，下面證明每個(gè)區(qū)間都能分配到一個(gè)可用資源。 命題 處理完第 ? ?1?ii 個(gè)區(qū)間后，某最優(yōu)解此時(shí)的狀態(tài) iS? 不優(yōu)于運(yùn)行該算法后此時(shí)的狀態(tài) iS 。設(shè)處理第 i 個(gè)區(qū)間時(shí)，該算法分配的資源是 ? ?11 jSi? ,在最優(yōu)解中分配的資源為 ? ?21 jSi? 。 ⑴當(dāng) 21 jj?? 時(shí)： ? ? ? ? ? ? ? ?jSjSjSjS iiii ????? ?? 11 ； ⑵當(dāng) 12 jjj ?? 時(shí)： ? ? ? ? ? ? ? ? ? ?jSjSjSjSjS iiiii ???????? ??? 1111 ； 8 ⑶當(dāng) djj ??1 時(shí)： ? ? ? ? ? ? ? ?jSjSjSjS iiii ??????? ?? 11 11 ； ⑷當(dāng) dj? 時(shí)： ? ? ? ? ? ?iejSjS ii ??? 。最優(yōu)解肯定能給該區(qū)間分配到資源，設(shè)為 ? ?01 jSi?? 。 綜上所述，該算法可以成功的構(gòu)造出正好 使用 d 個(gè)資源的一組解，而根據(jù)命題 d ，故該解是用到資源數(shù)量最少的解。每次處理某個(gè) 區(qū)間 時(shí)，可以在 ? ?dOlog 時(shí)間內(nèi)找到合適資源，并在 ? ?dOlog 時(shí)間內(nèi)修改該 資源結(jié)束時(shí)間。 例題 2： 2022年廣東省大學(xué)生程序競賽試題 Problem B 題目大意： 一個(gè)港口被分成了 ? ?101 ??mm 個(gè)區(qū)域，每個(gè)區(qū)域最多允許同 時(shí)?？?9 ? ?10000?rr 艘船，每艘船都只能停靠在特定的一個(gè)區(qū)域?？梢园汛醋饕粋€(gè)區(qū)間，則該問題是問題 2的一個(gè)變化：規(guī)定使用資源的數(shù)量 r ，問最多能選出多少區(qū)間。 在前面的證明中我們已經(jīng)證明了選擇資源的局部最優(yōu)性，唯一剩余的問題是區(qū)間的取舍。 有 n 個(gè)長度固定、但位置可變的區(qū)間，將它們?nèi)糠胖迷?),0[ ?? 上。 算法： 將 所有區(qū)間按最終期限從小到大排序，順序安排各區(qū)間，使中間沒有空閑段。 若在某最優(yōu)解中，兩相鄰區(qū)間 i 、 1?i 之間有空閑段，可將將 1?i 、 2?i 、?、n 全部往左移，直至 i 、 1?i 之間沒有空閑段。證畢。證畢。設(shè)區(qū)間 id 的左端點(diǎn)坐標(biāo)為 0t ，若交換兩 11 區(qū)間， 則原來兩區(qū)間的右端點(diǎn)坐標(biāo)為 ii ttf ?? 0 ， 101 ?? ??? iii tttf ，現(xiàn)在則分別為101 ?? ??? ii ttf ， 10 ????? iii tttf 。證畢。 一般在區(qū)間位置可變時(shí)，最優(yōu)解中各區(qū)間位置常常是按照最終期限排序，交換最終期限互為逆序的區(qū)間總能使結(jié)果更優(yōu)。問掛墜最多能由多少個(gè) 綴珠組成，并求出滿足綴珠數(shù)量最多時(shí)掛墜質(zhì)量的最小值。 根據(jù)原 問題，容易證明下面這個(gè)結(jié)論：顯然必有一個(gè)最有解，它的區(qū)間按最后期限 ii CW? 排序，連續(xù)地放置在 ),0[ ?? 上。則對(duì)于任意一個(gè)合法的 ],[ jif ，做下面的兩個(gè)動(dòng)態(tài)轉(zhuǎn)移：若第 1?i 個(gè)區(qū)間不選：? ? ? ? ? ?? ?jifjifjif ,1m i n,1 ??? ；若 1],[ ?? iCjif ， 則 可 以 選 擇 該 區(qū) 間 ：? ? ? ? ? ?? ?1,1,1m i n1,1 ??????? iWjifjifjif 。故每次從 ??ig 遞推 ? ?1?ig 時(shí)，可以進(jìn)行如下的兩個(gè)操作：⑴找到兩個(gè)位置，? ?? ?1,|m in ??? iWjigjleft ， ? ?? ?1,|max ??? iCjifjrig h t ；⑵刪除 ? ?1?rightg ，將? ?1?leftg , ? ?2?leftg ,? , ? ?rightg 的值向后平移到 ? ?2?leftg , ? ?3?leftg ,? , ? ?1?rightg ，并將 ? ?1?leftg 的值修改為 1?iW 。 算法 2： 維護(hù)一個(gè)按 ii CW? 排序的有序表，初始為空。 實(shí)現(xiàn)： 算法的瓶頸在有序表的維護(hù)上。 例題 ： Europe Southeastern 2022 Problem D 題目大意： 一家銀行收到了 ? ?100000 ?? NN 個(gè)貸款申請(qǐng)，每個(gè)貸款都最晚要在? ?100000 ?? ii dd 時(shí)完成，利潤為 ip 。可以用與例題 算法 2類似的 貪心算法解決該問題。處理第 i 個(gè)區(qū)間時(shí)，若可以選擇該區(qū)間（即 ? ? Lisdi i ???? ,0 ），則將該區(qū)間放置到一個(gè) i 最大的一個(gè)位置，即??? ?Lisiidi ??? |max0 ，否則就不選擇該區(qū)間。 優(yōu)化 2： 每次 ??? ?0?iis 的值增加后，若 ?? Lis ? ，則將之所屬集合與前面的 ? ?1?is 所屬集合合并成一個(gè)新集合。 第 1種優(yōu)化由于用到了線段樹，不論在空間上還是在時(shí)間上都有著巨大的系 15 數(shù)；而第 2種優(yōu)化用到的空間非常小，且在時(shí)間效率和編程復(fù)雜度兩方面都比第1種好很多。 證明： 顯然，該算法最后選出來的區(qū)間 完全覆蓋 ? ?ts, ，下面證明所選出 區(qū)間的數(shù)量是最少的。對(duì)于 1?i ，命題顯然為真，因?yàn)樗惴ǖ谝粋€(gè)選擇的區(qū)間是能覆蓋點(diǎn) s 的區(qū)間中右端點(diǎn)坐標(biāo)最大的那個(gè)。證畢。根據(jù)該算法， tfg mm ?? ，因此該最優(yōu) 解不可能覆蓋 t ，產(chǎn)生矛盾。時(shí)間復(fù)雜度：排序 ? ?nnO log +掃描??nO = ? ?nnO log 。如圖所示： 17 分析： 顯然覆蓋整個(gè)草坪的充要條件是要能覆蓋上邊界。詢問每只小海龜它是第幾名，它會(huì)回答你兩個(gè)數(shù)： iiba, ，分別表示在它前面的小海龜數(shù)和在它后面的小海龜數(shù)?？梢杂?jì)算出每個(gè)區(qū)間最多能有多少只海龜，把數(shù)值看做區(qū)間的“權(quán)”。 實(shí)現(xiàn)： 由于上述所有操作的排序關(guān)鍵字都在 N,...