算法合集之《淺談信息學競賽中的區(qū)間問題》

1、淺談信息學競賽中的區(qū)間問題華東師大二附中周小博 【摘要】本文對一些常用的區(qū)間問題模型做了簡單介紹，包括一些算法及其正確性的證明，并從國際、國內的信息學競賽與大學生程序設計競賽中選了近10道相關例題，進行簡要分析?！娟P鍵字】區(qū)間模型 轉化 貪心 動態(tài)規(guī)劃 優(yōu)化【引言】在信息學競賽中，有很多問題最終都能轉化為區(qū)間問題：例如從若干個區(qū)間中選出一些滿足一定條件的區(qū)間、將各個區(qū)間分配到一些資源中、或者將一些區(qū)間以某種順序放置等。這類問題變化繁多，解法各異，需要用到貪心、動態(tài)規(guī)劃等算法，并可以用一些數(shù)據(jù)結構優(yōu)化算法。本文將從幾個方面對區(qū)間問題做一個簡單的介紹，給出一些算法及其正確性的證明，具體分如下幾個方

2、面進行討論：1.最大區(qū)間調度問題2.多個資源的調度問題3.有最終期限的區(qū)間調度問題4.最小區(qū)間覆蓋問題5.帶權區(qū)間調度、覆蓋問題6.區(qū)間和點的有關問題我們將對上述每個問題都給出基本模型、算法、證明及其實現(xiàn)，并從ACM-ICPC、CEOI、CTSC等比賽中選出了近10道相關例題，進行簡要分析，有的例題還給出了各種不同的算法及其時間效率的分析。本文中所討論的問題主要由兩個部分組成，一部分為近幾年來各類競賽題的歸納總結，另一部分來自于參考文獻?！菊摹?.最大區(qū)間調度問題數(shù)軸上有個區(qū)間，選出最多的區(qū)間，使得這些區(qū)間不互相重疊。算法：將所有區(qū)間按右端點坐標從小到大排序，順序處理每個區(qū)間。如果它與當前已

3、選的所有區(qū)間都沒有重疊，則選擇該區(qū)間，否則不選。證明：顯然，該算法最后選出的區(qū)間不互相重疊，下面證明所選出區(qū)間的數(shù)量是最多的。設為該算法所接受的第個區(qū)間的右端點坐標，為某最優(yōu)解中的第個區(qū)間的右端點坐標。命題1.1 當時，該算法所接受的第個區(qū)間的右端點坐標某最優(yōu)解中的第個區(qū)間的右端點坐標。該命題可以運用數(shù)學歸納法來證明。對于，命題顯然為真，因為算法第一個選擇的區(qū)間擁有最小右端點坐標。令，假定論斷對為真，即。則最優(yōu)解的第個可選區(qū)間所組成的集合包含于執(zhí)行該算法時第個可選區(qū)間所組成的集合；而當算法選擇第個區(qū)間時，選的是在可選區(qū)間中右端點坐標最小的一個，所以有。證畢。設該算法選出了個區(qū)間，而最優(yōu)解選出了

4、個區(qū)間。命題1.2 最優(yōu)解選出的區(qū)間數(shù)量=該算法選出的區(qū)間數(shù)量。假設，根據(jù)命題1.1，有。由于，必然存在某區(qū)間，在之后開始，故也在之后開始。而該算法一定不會在選了第個區(qū)間后停止，還會選擇更多的區(qū)間，產生矛盾。所以,又因為是最優(yōu)解選出區(qū)間個數(shù)，所以。綜上所述，算法選出的區(qū)間是最優(yōu)解。實現(xiàn)：在判斷某個區(qū)間與當前已選的所有區(qū)間是否重疊時,可以直接判斷是否和所選的最后一個區(qū)間是否重疊。時間復雜度：排序+掃描=。 HYPERLINK l aSECTION1 例題1：Latin America - South America 2001 Problem A題目大意：基因是由許多外顯子（exon）組成，每個外

5、顯子都有一個起始位置和一個結束位置。兩個外顯子能夠互相聯(lián)接必須滿足某個外顯子的起始位置在另一個外顯子的結束位置之后。給出個外顯子，要求找到一條由外顯子組成的基因鏈，使得外顯子數(shù)量最多。分析：將每個外顯子看作一個區(qū)間，兩端點坐標分別為外顯子的起始、結束位置。則現(xiàn)在的問題和原問題基本相同，只是端點上也不能重疊。這里就不寫算法了。2.多個資源的調度問題有個區(qū)間和無限多的資源，每個資源上的區(qū)間之間不互相重疊。將每個區(qū)間都分配到某個資源中，使用到的資源數(shù)量最小。定義區(qū)間集合深度為包含任意一點的區(qū)間數(shù)量的最大值，則顯然有：命題2.1 需要的資源數(shù)至少為。設區(qū)間,全部包含某一點，則必須把這些區(qū)間分配到不同資

6、源中，故至少需要個資源。其實競賽中也出現(xiàn)過計算區(qū)間集合深度的題目，如 HYPERLINK l aSECTION2_0 North America Northeast 2003 Problem E。下面給出計算區(qū)間集合深度的算法。的計算方法：將每個區(qū)間拆成兩個事件點，按坐標從小到大排序，順序處理每個區(qū)間。記錄一個值，表示當前點被包含次數(shù)。每次遇到區(qū)間的左端點就+1，遇到右端點就-1。的值就是在該過程中的最大值。注意兩個相同坐標不同類型的事件點的位置關系和區(qū)間是否能在端點處重疊有關，這在排序過程中應該注意。時間復雜度為排序+掃描=由此可得出一個構造算法。算法1：計算出。將所有區(qū)間按左端點坐標從小到

7、大排序，順序處理每個區(qū)間。處理某個區(qū)間時，排除在它前面且與之重疊的區(qū)間所用到的資源，然后在1,2,3,這些資源中任意分配一個未被排除的資源。證明：設排序后的個區(qū)間分別為,命題2.2 每個區(qū)間都能分配到一個資源?？紤]任何一個區(qū)間，假設存在個區(qū)間在它前面且與之重疊。一定有，否則由于這個區(qū)間都包含的起始時刻，與的定義矛盾。故有，從而在個資源中至少有一個資源沒被這個區(qū)間排除。所以對于每個區(qū)間，都至少有一個可分配資源。證畢。命題2.3 沒有兩個互相重疊的區(qū)間被分配到了同一個資源?？紤]任意兩個互相重疊的區(qū)間、，其中。當算法在處理區(qū)間時，區(qū)間所用資源已經(jīng)被排除，所以不會被分配到同一資源。綜上所述，該算法可以

8、成功的構造出正好使用個資源的一組解，而根據(jù)命題2.1，所用資源的下限是，故該解是用到資源數(shù)量最少的解。實現(xiàn)：區(qū)間分配資源時，如果直接做排除，則時間復雜度為，當然可以通過記錄每個資源的最大右端點坐標以將時間復雜度降為；由于可以每次找一個最大右端點坐標最小的資源，故可以用一個優(yōu)先隊列來儲存每個資源的最大右端點坐標。用二叉堆實現(xiàn)該優(yōu)先隊列，每次查找最小值的時間復雜度為，修改關鍵字的時間復雜度為，分配資源操作的時間復雜度也就降為。故總時間復雜度為：的計算+排序+分配資源=。其實這里可以不計算出，而通過不斷地增加資源數(shù)量來使所有區(qū)間都能分配到資源。該算法同時也證明了以下命題：命題2.4 用到的資源數(shù)量的

9、最小值為區(qū)間集合深度。基于這個命題，我們很容易想到另外一種算法。算法2：計算。將所有區(qū)間按右端點坐標從小到大排序，順序處理每個區(qū)間。對于每個區(qū)間，都在1,2,3,這些資源中分配一個可用的且右端點坐標最大的資源。證明：顯然每個資源上的區(qū)間都不互相重疊，下面證明每個區(qū)間都能分配到一個可用資源。用一個元素個數(shù)為的有序表（表中元素始終從小到大排序），記錄處理個區(qū)間后，各個資源的最大右端點坐標（當某個資源從沒被用過時，可認為值為）。同樣用表表示處理個區(qū)間后，某最優(yōu)解的狀態(tài)（根據(jù)命題2.5，該表中元素個數(shù)也是）。狀態(tài)不優(yōu)于狀態(tài)指。命題2.5 處理完第個區(qū)間后，某最優(yōu)解此時的狀態(tài)不優(yōu)于運行該算法后此時的狀態(tài)

10、。該命題可以運用數(shù)學歸納法來證明。對于，命題顯然為真，因為第一個區(qū)間無論分配哪個資源，狀態(tài)都是一樣的。令，假定論斷對為真，即。設處理第個區(qū)間時，該算法分配的資源是,在最優(yōu)解中分配的資源為。設第個區(qū)間的右端點坐標為。表更新為：；表更新為：。而該算法分配的資源在所有可分配資源中擁用最大右端點坐標，故區(qū)間的左端點坐標小于，又，所以。當時：；當時：；當時：；當時：。所以有，證畢。命題2.6 每個區(qū)間都能分配到一個資源。處理第個區(qū)間時，狀態(tài)可用表示。最優(yōu)解肯定能給該區(qū)間分配到資源，設為。根據(jù)命題2.5，。則運行該算法時，至少可以給該區(qū)間分配資源。證畢。綜上所述，該算法可以成功的構造出正好使用個資源的一組

11、解，而根據(jù)命題2.1所用資源的下限是，故該解是用到資源數(shù)量最少的解。實現(xiàn)：考慮如何分配資源。如果直接記錄每個資源的最大右端點坐標，時間復雜度為。可以用證明中所提到的有序表，用一個平衡二叉樹來維護它。每次處理某個區(qū)間時，可以在時間內找到合適資源，并在時間內修改該資源結束時間。這樣做的總時間復雜度也是。第一個構造算法證明了最少所用資源的數(shù)量，并用編程復雜度較低的方法構造出了可行解。第二個貪心算法是基于第一個算法的結論得到的，編程復雜度也比第一種高，然而利用它的局部最優(yōu)性，還可以附加更多的條件。 HYPERLINK l aSECTION2 例題2：2004年廣東省大學生程序競賽試題 Problem

12、B題目大意：一個港口被分成了個區(qū)域，每個區(qū)域最多允許同時?？克掖?，每艘船都只能?？吭谔囟ǖ囊粋€區(qū)域。有艘船，已知每條船的到達時刻、離開時刻和它應該進入的區(qū)域。求一個調度方案使得能有最多的船得以?？俊７治觯猴@然每個區(qū)域都可以單獨處理?？梢园汛醋饕粋€區(qū)間，則該問題是問題2的一個變化：規(guī)定使用資源的數(shù)量，問最多能選出多少區(qū)間。在算法2上稍加改動即可得出該題的算法。算法：將所有區(qū)間按右端點坐標從小到大排序，順序處理每個區(qū)間。對于每個區(qū)間，若能找到可用資源，則將該區(qū)間安排到一個可用的且右端點坐標最大的資源；若找不到，則不去選它。在前面的證明中我們已經(jīng)證明了選擇資源的局部最優(yōu)性，唯一剩余的問題是區(qū)間的取

13、舍。如果該算法選擇了某區(qū)間，而某最優(yōu)解中沒有選它，顯然最優(yōu)解選擇了一個與該區(qū)間重疊且右端點坐標大于等于它的區(qū)間，我們用替換,就構成了一個包含的最優(yōu)解；如果該算法沒有選擇某區(qū)間，顯然最優(yōu)解也不會選擇該區(qū)間。故該算法得出的解就是最優(yōu)解。實現(xiàn)：還是利用平衡二叉樹維護資源信息并尋找合適資源，處理每個區(qū)間的時間復雜度是，故總時間復雜度為：排序+處理區(qū)間=。3.有最終期限的區(qū)間調度問題有個長度固定、但位置可變的區(qū)間，將它們全部放置在上。每個區(qū)間有兩個已知參數(shù)：長度和最終期限，設為其右端點坐標。定義，。放置所有區(qū)間，使它們不互相重疊且最大延遲最小。算法：將所有區(qū)間按最終期限從小到大排序，順序安排各區(qū)間，使中

14、間沒有空閑段。證明：由于該算法所有區(qū)間都順序放置，因此區(qū)間之間不互相重疊。下面證明該算法求出的最小。命題3.1 存在一個沒有空閑段的最優(yōu)解。若在某最優(yōu)解中，兩相鄰區(qū)間、之間有空閑段，可將將、全部往左移，直至、之間沒有空閑段。顯然、減小，即、減小。所以此時的最大延遲一定小于等于原先的，又已是最小值，所以。因此任何一個有空閑段的最優(yōu)解不斷地進行上述操作后終會變成一個沒有空閑時間的最優(yōu)解。證畢。命題3.2 任何一個既沒有逆序、又沒有空閑段的解有著相同的最大延遲。如果解中既沒有逆序、又沒有空閑段，那么相同最終期限的區(qū)間只有在次序上可能不同。而這些區(qū)間的最大延遲只和最后一個區(qū)間的右端點坐標有關，區(qū)間的次

15、序卻并不影響最后一個區(qū)間的右端點坐標，所以最大延遲始終相同。證畢。命題3.3 既沒有逆序、又沒有空閑段的解是最優(yōu)解。根據(jù)命題3.1，存在一個沒有空閑段的最優(yōu)解。假設某最優(yōu)解中相鄰的某兩區(qū)間、為逆序關系，即有。設區(qū)間的左端點坐標為，若交換兩區(qū)間，則原來兩區(qū)間的右端點坐標為，現(xiàn)在則分別為，。設兩區(qū)間在交換前后的延遲分別為、。因為，所以、不優(yōu)于、。因此一個存在逆序的解交換相鄰的逆序項可以使之更優(yōu)，只要將一個有逆序的解不斷進行上述操作后都能成為一個無逆序的解。證畢。綜上所述，該算法成功構造了一個最優(yōu)解。實現(xiàn)：按算法直接模擬。時間復雜度：排序+掃描=。一般在區(qū)間位置可變時，最優(yōu)解中各區(qū)間位置常常是按照最

16、終期限排序，交換最終期限互為逆序的區(qū)間總能使結果更優(yōu)。當然區(qū)間帶權時，要另外考慮。 HYPERLINK l aSECTION3_1 例題3.1：CTSC 2007 DAY2 pendant題目大意：有粒綴珠，每粒綴珠有兩個參數(shù)：掛鉤的最大承受重量和本身重量。將綴珠經(jīng)掛鉤連接后掛起形成掛墜，要求每粒綴珠下方的綴珠重量之和不能超過它掛鉤的最大承受重量。問掛墜最多能由多少個綴珠組成，并求出滿足綴珠數(shù)量最多時掛墜質量的最小值。分析：把每粒綴珠看作一個長度為的區(qū)間，這些區(qū)間的位置是可變的。則問題轉化為：選出最多的區(qū)間，并將它們不互相重疊地放置在上，使得左端點坐標不能超過。在保證區(qū)間數(shù)量最大時，需求出最大

17、右端點坐標的最小值。根據(jù)原問題，容易證明下面這個結論：顯然必有一個最有解，它的區(qū)間按最后期限排序，連續(xù)地放置在上。（證明和原問題的證明方法類似）在這個結論的基礎上，可以得出以下兩種算法。算法1：容易想到一個的動態(tài)規(guī)劃。將區(qū)間按的值從小到大排序，設為前個區(qū)間，選取了個區(qū)間后，最大右端點坐標的最小值。則對于任意一個合法的，做下面的兩個動態(tài)轉移：若第個區(qū)間不選：；若，則可以選擇該區(qū)間：。狀態(tài)數(shù)為，狀態(tài)轉移時間為，故時間復雜度為。然而僅僅是不夠的，還需要優(yōu)化。優(yōu)化：設,顯然不變時，隨著的增大而呈單調遞增（如果,那么肯定不是最大右端點坐標的最小值）。故每次從遞推時，可以進行如下的兩個操作：找到兩個位置，

18、；刪除，將,的值向后平移到, ，并將的值修改為。時間復雜度：用一棵平衡二叉樹維護，則從遞推的時間復雜度為，所以總時間復雜度為：排序+的維護=。該算法要用到平衡二叉樹，編程復雜度較大。其實仔細分析算法1，并加以改進，就可以得到一個貪心的算法。算法2：維護一個按排序的有序表，初始為空。將所有區(qū)間按長度從小到大排序，依次處理。處理某個區(qū)間時，若它能夠放入有序表，則選擇該區(qū)間并放入表中，否則不選擇。最后的表即是要求的狀態(tài)。實現(xiàn)：算法的瓶頸在有序表的維護上。如果直接模擬該表的所有操作，時間復雜度是。用線段樹來維護該表，可以在的時間里完成每個區(qū)間的取舍及插入操作（這些操作并不是非常容易實現(xiàn)，但與論文主題無

19、關，這里不再細寫）。因此，總時間復雜度為。 HYPERLINK l aSECTION3_2 例題3.2：Europe - Southeastern 2007 Problem D題目大意：一家銀行收到了個貸款申請，每個貸款都最晚要在時完成，利潤為。每個貸款需要一個單位時間處理，銀行在同一時間內最多可以接受個貸款。求如何安排才能獲得最大利潤。分析：將每個貸款申請看作一個單位長度、位置可變且?guī)嗟膮^(qū)間，則題目轉化為選出一些區(qū)間，將它們不互相重疊地放在個資源上，使利潤最大，且區(qū)間的左端點不得超過?？梢杂门c例題3.1算法2類似的貪心算法解決該問題。算法：將這些區(qū)間按照權值從大到小排序，順序處理每個區(qū)間。

20、設。由于區(qū)間都是單位長度的，我們可以用一維數(shù)組來記錄當前的情況，表示被覆蓋次數(shù)，根據(jù)題意有。處理第個區(qū)間時，若可以選擇該區(qū)間（即），則將該區(qū)間放置到一個最大的一個位置，即，否則就不選擇該區(qū)間。處理每個區(qū)間時，若直接模擬，時間復雜度是，最好還是做適當優(yōu)化。優(yōu)化1：若用一棵線段樹來維護數(shù)組，可以在的時間里處理每個區(qū)間。總時間復雜度為：排序+處理每個區(qū)間=。優(yōu)化2：每次的值增加后，若，則將之所屬集合與前面的所屬集合合并成一個新集合。處理第個區(qū)間時，它選擇的位置必是所在集合中的最前面的元素，（若最前面的元素是且，則表示該區(qū)間不能被選擇）。如果我們用并查集來實現(xiàn)集合的各種操作，維護它的時間復雜度可近似地

21、看作?？倳r間復雜度：排序+處理每個區(qū)間=。第1種優(yōu)化由于用到了線段樹，不論在空間上還是在時間上都有著巨大的系數(shù)；而第2種優(yōu)化用到的空間非常小，且在時間效率和編程復雜度兩方面都比第1種好很多。4.最小區(qū)間覆蓋問題有個區(qū)間，選擇盡量少的區(qū)間，使得這些區(qū)間完全覆蓋某線段。算法：將所有區(qū)間按左端點坐標從小到大排序，順序處理每個區(qū)間。每次選擇覆蓋點的區(qū)間中右端點坐標最大的一個，并將更新為該區(qū)間的右端點坐標，直到選擇的區(qū)間已包含。證明：顯然，該算法最后選出來的區(qū)間完全覆蓋，下面證明所選出區(qū)間的數(shù)量是最少的。設為該算法所接受的第個區(qū)間的右端點坐標，為某最優(yōu)解中第個區(qū)間的右端點坐標。命題4.1 當時：該算法所

22、接受的第個區(qū)間的右端點坐標某最優(yōu)解中的第個區(qū)間的右端點坐標。該命題可以運用數(shù)學歸納法來證明。對于，命題顯然為真，因為算法第一個選擇的區(qū)間是能覆蓋點的區(qū)間中右端點坐標最大的那個。令，假定論斷對為真，即，最優(yōu)解中選的第個區(qū)間的右端點坐標為,設它的左端點坐標為。由于該區(qū)間覆蓋，即。當時，由于，有；當時，有，此時最優(yōu)解所選擇的區(qū)間覆蓋點,又算法選擇的第個區(qū)間是右端點坐標最大的那個，故。證畢。設該算法選出了個區(qū)間，而最優(yōu)解選出了個區(qū)間。命題4.2 最優(yōu)解選出的區(qū)間數(shù)量=該算法選出的區(qū)間數(shù)量。假設，根據(jù)命題4.1，有。根據(jù)該算法，因此該最優(yōu)解不可能覆蓋，產生矛盾。所以,又因為是最優(yōu)解中選出區(qū)間個數(shù)，所以。

23、綜上所述，算法選出的區(qū)間是最優(yōu)解。實現(xiàn)：選擇區(qū)間可以通過線性掃描來實現(xiàn)。時間復雜度：排序+掃描=。 HYPERLINK l aSECTION4 例題4：ACM/ICPC Regional Warm-up Contest 2002 Problem E題目大意：有一塊草坪，長為，寬為，在它的中心線的位置處裝有個點狀的噴水裝置。每個噴水裝置噴水的效果是以它為中心半徑為的圓都被潤濕。請選擇盡量少的噴水裝置，把整個草坪全部潤濕。如圖所示：分析：顯然覆蓋整個草坪的充要條件是要能覆蓋上邊界。將每個噴水設置能覆蓋的一段上邊界看成一個區(qū)間，轉化后的問題就是原問題。5.帶權區(qū)間調度、覆蓋問題若區(qū)間帶權，如何解決調

24、度、覆蓋一類問題呢？這時，剛才一直用的貪心算法已經(jīng)不再普遍適用，大部分情況下，只能用更一般性的方法動態(tài)規(guī)劃。 HYPERLINK l aSECTION5_1 例題5.1：Europe - Northeastern Europe 2004 Problem J題目大意：有只可愛的小海龜在賽跑。詢問每只小海龜它是第幾名，它會回答你兩個數(shù)：，分別表示在它前面的小海龜數(shù)和在它后面的小海龜數(shù)。接著你發(fā)現(xiàn)其中有些小海龜對你撒了謊，因為根據(jù)他們的說法你根本沒法給他們排隊！但是你是善良的，你不希望有很多小海龜在撒謊，想找出最少有哪幾只小海龜在撒謊。（注意：小海龜?shù)拿慰赡苁遣⒘械模。┓治觯喝粢恢缓｝斦f了真話，那

25、么該海龜?shù)奈恢靡欢ㄊ窃趨^(qū)間上。若有只海龜選擇了相同的區(qū)間，則根據(jù)并列關系，該區(qū)間最多能同時擁有只海龜?？梢杂嬎愠雒總€區(qū)間最多能有多少只海龜，把數(shù)值看做區(qū)間的“權”。則問題轉化為，在一些帶權區(qū)間中，選出權和最大的區(qū)間，使它們之間不能互相重疊。算法：算出每個出現(xiàn)過的區(qū)間的“權”，接下來的算法就是動態(tài)規(guī)劃了。先按右端點坐標從小到大排序，令為在區(qū)間左邊的且與之無公共點的最大區(qū)間編號，設狀態(tài)為在前個區(qū)間中可選出區(qū)間的最大權和，則狀態(tài)轉移方程為，說真話海龜?shù)淖畲髷?shù)量就是最后一個區(qū)間的值。實現(xiàn)：由于上述所有操作的排序關鍵字都在中，所以可以使用時間復雜度為的基數(shù)排序，其它各操作也均能在時間內完成（具體細節(jié)留給

26、讀者思考）。所以，總時間復雜度為。 HYPERLINK l aSECTION5_2 例題5.2：USACO 2005 dec silver題目大意：倉庫從第秒到第秒的任意時刻都需要有人打掃，包括和，。有個工人前來應聘打掃倉庫的工作，每人給出自己可以工作的時間段：從第秒到第秒（包括第秒和第秒），需要支付工資元。，。每個應聘者，你能夠錄用或者不錄用，但不能只雇傭他提出的一部分時間。一旦錄用，你就得支付他提出的元給他?，F(xiàn)在要保證從秒到第秒的任意時刻都得有人打掃，問最少要付多少工資。分析：將每個人的打掃時間看作一個左右端點分別為和，且權為區(qū)間。則問題轉化為：選出一些區(qū)間，使它們覆蓋上的所有整數(shù)點，求權

27、和最小值。算法：這道題很容易想到一個的動態(tài)規(guī)劃算法。將所有區(qū)間按右端點坐標從小到大排序，順序處理每個區(qū)間。用表示在前個區(qū)間中選擇，且第個區(qū)間必須選時，覆蓋的權和最小值。則狀態(tài)轉移方程為：,最后的結果就是。第一種優(yōu)化：對于這個狀態(tài)轉移方程，很容易想到用線段樹優(yōu)化的方法。建立一棵范圍是的線段樹，葉子節(jié)點是一個個整點坐標。每得到一個的值，就將它插入在處，并更新最小值。計算的值時只要選取區(qū)間中的最小值進行狀態(tài)轉移即可。算法時間復雜度為：排序+維護線段樹=，故總時間復雜度是。這樣做編程復雜度較高，且時間效率亦不是很好（雖然可以通過離散化稍微降低一點時間復雜度，但仍然系數(shù)巨大）。仔細分析，可以找到更好的優(yōu)

28、化方法。第二種優(yōu)化：建立一個棧，表示處在棧中第個位置的區(qū)間。假設棧中已經(jīng)有個區(qū)間，保持棧中區(qū)間值的單調性：。每次要將第個區(qū)間壓入棧中時，做這樣的操作：while poppush 計算的值時，可以借助棧找到一個區(qū)間，使且最小，進行狀態(tài)轉移。根據(jù)棧中元素的單調性，這里可以用二分查找。由于一共個區(qū)間，每個區(qū)間進棧、出棧最多一次，故棧的維護的時間復雜度為。在任何時間內，棧內區(qū)間個數(shù)不超過，故一次二分查找復雜度為。綜上所述，該方法的總時間復雜度為。由于棧、二分查找的系數(shù)比線段樹小很多，且棧內區(qū)間個數(shù)很少有達到的情況，故這種優(yōu)化比前面的要好很多。第三種優(yōu)化：以左端點為關鍵字從小到大排序，按順序依次處理每個

29、區(qū)間。維護一個以為關鍵字的優(yōu)先隊列。處理區(qū)間時，只要最小關鍵字區(qū)間的右端點坐標小于，就刪除。重復上述操作，直到當前區(qū)間能和最小關鍵字區(qū)間進行狀態(tài)轉移。狀態(tài)轉移后，將區(qū)間插入優(yōu)先隊列。由于每個區(qū)間最多只進出隊列一次，故一共要進行次插入操作和次刪除操作。用二叉堆實現(xiàn)該優(yōu)先隊列，插入和刪除操作的時間復雜度都是，因此總時間復雜度為：排序+動態(tài)規(guī)劃+維護二叉堆=。該優(yōu)化時間復雜度的系數(shù)介于前兩種優(yōu)化之間，然而對于實現(xiàn)而言，使用Pascal的編程量和用第一種優(yōu)化差不多，而使用C/C+就可以大大減少編程量。6.區(qū)間和點的有關問題有個區(qū)間，個點。若某區(qū)間包含了某點，則構成一對匹配關系。選出最多的區(qū)間和相同數(shù)量

30、的點，使對應的區(qū)間和點構成匹配關系。該問題雖然可以建立一個二分圖匹配模型，但時間復雜度顯然太高，應該充分利用區(qū)間的性質。算法：將所有的點按坐標從小到大排序，順序處理每個點。每次都在剩余區(qū)間中取出包含該點且右端點坐標最小的區(qū)間與之配對，若沒有則不選擇該點。證明：設某最優(yōu)解的匹配集合為，該算法求出的一對匹配是第個點和第個區(qū)間。命題6.1 和至少有一個出現(xiàn)在里。假設它們都不出現(xiàn)在里，則中還可以加上一對新的匹配，與為最優(yōu)解矛盾。命題6.2 該算法求出的所有匹配都可以出現(xiàn)在另一最優(yōu)解中。仍然考慮該算法求出的任意匹配，若，則可分以下三種情況討論：若出現(xiàn)在里、未出現(xiàn)在里，設中與匹配。在中可刪除，并添加。若出

31、現(xiàn)在里、未出現(xiàn)在里，設中與匹配。在中可刪除，并添加。若和都出現(xiàn)在里，設中與匹配、與匹配。根據(jù)該算法，顯然有，所以可將的這兩組匹配改為和。因此解可經(jīng)過一系列的轉化變成解，且由于轉化時匹配數(shù)始終保持不變，所以也為最優(yōu)解，因此該算法中的所有匹配都在其中。根據(jù)該算法，顯然不可能有匹配在中卻不在該算法所求出的匹配中，故該算法求出的匹配集就是，為一最優(yōu)解。實現(xiàn)：選點時直接模擬的時間復雜度為，可用與例題5.2的優(yōu)化3相似的方法來對該算法進行優(yōu)化。做預處理，以區(qū)間左端點為關鍵字，對它們排序，得到一個有序表。維護一個優(yōu)先隊列，以區(qū)間的右端點作為關鍵字。將所有點按坐標從小到大排序，依次處理各點。處理某點時，先插入

32、左端點小于等于該點坐標且從未進入過隊列的區(qū)間（插入?yún)^(qū)間順序和有序表一致，故每次可在時間內判斷是否需要插入），再刪除右端點小于該點坐標的區(qū)間，將優(yōu)先隊列里的區(qū)間中右端點坐標最小的與該點匹配并刪除。由于每個區(qū)間只進出隊列一次，故一共要進行次插入操作和次刪除操作。用二叉堆實現(xiàn)該優(yōu)先隊列，則每次操作的時間復雜度降為。因此，該算法總的時間復雜度為：計算有序表+點排序+維護優(yōu)先隊列+處理每個點=。 HYPERLINK l aSECTION6_1 例題6.1：CEOI 2004 trips題目大意：有個團隊和條旅行線路，每個團隊最多只能選一條旅行線路，每條旅行線路至多只能供一個團隊選擇。第個團隊有人數(shù)，第條

33、旅行線路有人數(shù)下限和上限，只有當時，第個團隊才能選擇第條旅行線路。求團隊和旅行線路的最大配對數(shù)。分析：將團隊能去的旅行線路看作區(qū)間，將每條旅行線路看做點。轉化后的問題和原問題完全一樣，這里就不再寫算法了。 HYPERLINK l aSECTION6_2 例題6.2：CEOI 2000 Enlightened Landscape題目大意：在一片山的上空，高度為處有個處于不同水平位置的燈泡（如圖）。如果山的邊界上某一點與燈的連線不經(jīng)過山上的其他點，我們稱燈可以照亮該點。開盡量少的燈，使得整個山景都被照亮。山景是一條折線，折點數(shù)。算法：容易看出，照亮整個山景的充分必要條件是照亮所有的折點。我們可以在

34、的時間內算出某燈泡是否能照亮某折點。由于每個燈泡照射到的折點是非連續(xù)的，較難處理，我們不妨考慮每個折點能被那些燈泡照到，發(fā)現(xiàn)都是連續(xù)的段。于是題目轉化為：給定個區(qū)間，以及個點，區(qū)間的兩端點都是這個點之一。選出最少的點，使每個區(qū)間都至少包含一個所選的點。顯然那些包含其它區(qū)間的區(qū)間已不必考慮，可以刪去。這一步可以這么實現(xiàn)：將所有區(qū)間按右端點從小到大，若右端點相同則按左端點從大到小排序，從前往后依次處理。維護一個值，記錄當前已處理區(qū)間左端點坐標的最大值，初始值為。處理某個區(qū)間時，若該區(qū)間的左端點小于等于，則刪除該區(qū)間，否則更新。將剩余區(qū)間按位置重新排序，順序處理各區(qū)間。若區(qū)間已包含某點，則不去考慮，

35、否則選擇區(qū)間的右端點。優(yōu)化：若確定了區(qū)間，則接下來選點的復雜度顯然為,時間效率的優(yōu)劣取決于預處理每個折點能被哪段燈泡照到的時間。如果直接模擬，時間復雜度為，對該題的數(shù)據(jù)規(guī)模而言，這個算法已經(jīng)可以AC了。其實可以用棧將預處理的時間復雜度進一步降低：先從左往右掃描，確定每個折點能被最左邊的哪個燈泡照到。對于第折點，進行這樣的操作（設棧中有個元素）：while折點的高度大于等于折點的高度or 線段（折點，折點）在折點上方pop算出射線（折點，折點）與直線的交點利用二分查找找到橫坐標大于等于的最左邊的燈泡（該燈泡就是能照到折點的最左邊的燈泡）push 同樣可以通過從左往右掃描求出每個折點能被最右邊的哪

36、個燈泡照到。由于每個折點最多進出棧一次，棧的維護需要的時間為，故預處理時間復雜度為：棧操作+二分查找=，總時間復雜度也就降為。【總結】區(qū)間問題通常要保持有序性，排序關鍵字的選擇非常重要。只有選擇了合適的關鍵字，才更容易解決這類問題。區(qū)間問題的解決方法主要有兩種：貪心（構造）；動態(tài)規(guī)劃。雖然后者能解決更多的問題，但往往前者擁有更好的時間效率，實現(xiàn)或優(yōu)化起來更加容易。區(qū)間問題的優(yōu)化大多可以用到線段樹，極少數(shù)要用到平衡二叉樹，但往往這并不是最佳的優(yōu)化方法。要學會在解題過程中發(fā)現(xiàn)更好的規(guī)律，用編程復雜度和時間效率俱佳的方法進行優(yōu)化，如利用決策的單調性，或運用一些簡單數(shù)據(jù)結構維護等?！緟⒖嘉墨I】1算法藝

37、術與信息學競賽 劉汝佳 黃亮 著 清華大學出版社2計算機算法設計與分析 王曉東編著 電子工業(yè)出版社3算法設計 Jon Kleinberg，va Tardos 著 清華大學出版社4廣東省大學生程序設計競賽試題（2003-2005年）郭嵩山 黎俊瑜 林祺穎 著 電子工業(yè)出版社5CTSC 2007 Reports, By Guo Huayang6汪汀turtle解題報告2005集訓隊作業(yè)7. 朱晨光基本數(shù)據(jù)結構在信息學競賽中的應用 2006集訓隊論文【附錄】Latin America - South America 2001 Problem AGene AssemblyWith the large

38、amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, becau

39、se of the presence of junk DNA that interrupts the coding regions of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and thei

40、r lengths can be arbitrary.Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in t

41、he genomic sequence. We say that exon appears before exon j if the end of i precedes the beginning of j. The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that could be assembled to generate a gene.InputSeveral input instance

42、s are given. Each instance begins with the number 0 n 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most

43、 50000 basis. The input ends with a line with a single 0.OutputFor each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. The exons must follow the order of appearance (as defined in the statement of the p

44、roblem). If there is more than one chain with the same number of exons, your program can print anyone of them.Sample Input6340 500220 470100 300880 943525 556612 7763705 773124 337453 66502Sample Output3 1 5 6 42 3 1（ HYPERLINK l SECTION1 例題1）North America Northeast 2003 Problem EWho is Still Alive?

45、At various points in history a number of presidents (former and the current president) have been alive. For example, currently there are six living presidents: Ford, Carter, Reagan, George the Second (George H. Bush), Clinton, and George the Third (George W. Bush). Note: George Washington was George

46、 the First.Write a program that takes as input the name, inauguration date, and date of death (if appropriate) of several presidents and produces as output the periods of time when the maximum number of current or former presidents are alive, together with the names of those presidents in alphabetic

47、al order. Note, there may be several such intervals and all must be listed in chronological order.InputThe input to your program will start with a line that contains a single integer, N, that specifies the number of presidents to be considered. Each of the following N lines of input describes a sing

48、le president. An input line for a president will consist of an identifier consisting of letters only. The identifier will be followed by the inauguration date, and by an optional date of death. Dates will be expressed in the form yyyy - mm - dd where yyyy represents a year, mm represents a month, an

49、d dd represents a day. If the president is still alive, no death date will be given. One or more white space characters will separate tokens on the input line. Note that if a president was inaugurated more than once, they may appear in the input more than once; remember, however, that once a preside

50、nt, always a president.OutputThe output from the program will specify the period of time when the most presidents were alive, followed by the names in alphabetical order. If there are multiple intervals, the intervals will be listed in chronological order, separated by a blank line. Sample Input3Nix

51、on 1969-01-20 1994-04-22Ford 1974-01-20GWBush 2001-01-20Sample Output1969-1-20 to 1994-4-22FordNixon1974-1-20 to 2003-11-7FordGWBush（ HYPERLINK l SECTION2_0 問題2中曾提到）2004年廣東省大學生程序競賽試題 Problem BBerth Allocation(Input File: berth.in/Output File: berth.out)Singapore port is one of the busiest ports in t

52、he world. In 1994, Singapore maintained its position as the worlds busiest port in terms of shipping tonnage of ship arrivals. In that year, there were 101,107 ship arrivals with shipping tonnage of 678.6 million gross tons. One of the planning problems encountered at the post is to decide whether a

53、 given set of ships can be berthed in a section of the port with certain berthing constraints.The port is divided into m sections and no ship can berthed across a section. Ships arrive at the port at different times to be berthed. Every ship has an expected duration of stay which may be different fr

54、om another ship. You can berth a ship or not when it arrives. To berth a ship is to place the ship along the wharf line of a section. Once a ship if berthed, it will not be moved until its departure, that is, if two ships are in the same section and have a time overlap, they cannot share any part of

55、 the section. Whats more, the berthing of the ships cannot exceed the capacity of the section.To simplify the problem, we just consider the section as a rectangle with a length of L hundred meters and a width of W hundred meters. When a ship arrives, you can berth it at any available position in the

56、 section at that time, or you can reject berthing it according to your berthing plan. Now the problem becomes a packing model of 3 dimensions (length, width, time). Since the width of a section if the same as ships, we can just consider the problem in 2 dimensions (length, time).Here is the explanat

57、ion of the last data set in the sample input. The port has one section, which is 2 hundred meters long. There are four ships arriving at time 1,5,2,4 and departing at time 3,6,8,10 respectively. They are all berth in section one. Figure 2.2.1 and Figure 2.2.2 are two legal berthing plans, from which

58、 we can know the maximal number of berthed ships is 3.Figure 2.2.1 The Berthing Plan of 3 shipsFigure 2.2.2 The other Berthing Plan of 3 shipsMax, the consultant of the harbor bureau, thinks that it is a ZSU(Zappy Ships Unallocation) problem. As his name, Max wants to make a plan to maximize the tot

59、al number of berthed ships, in other words, minimize the number of unberthed ships. Just like other packing problems, it is difficult for Max to solve. But he believes that the best team of the contest is able to solve it both correctly and effectively. Do your guys want to be the best? Just try it.

60、Input:Input contains many test sets. A test data set is defined as follow:The first line of test data set is two integers: m and n, separated by one or more spaces(1m10, 1n100000). m is the number of sections in the port, and n is the number of ships.The next m lines, one positive integer r (that me