【正文】 證明： 由于該算法所有區(qū)間都順序放置，因此區(qū)間之間不互相重疊。下面證明該算法求出的 L 最小。 命題 存在一個(gè)沒有空閑段的最優(yōu)解。 若在某最優(yōu)解中，兩相鄰區(qū)間 i 、 1?i 之間有空閑段，可將將 1?i 、 2?i 、?、n 全部往左移，直至 i 、 1?i 之間沒有空閑段。顯然 1?if 、 2?if 、?、 nf 減小，即1?il 、 2?il 、?、 nl 減小。所以此時(shí)的最大延遲 L? 一定小于等于原先的 L ，又 L 已是最小值，所以 LL?? 。因此任何一個(gè)有空閑段的最優(yōu)解不斷地進(jìn)行上述操作后終會(huì)變成一個(gè)沒有空閑時(shí)間的最優(yōu)解。證畢。 命題 任何一個(gè)既沒有逆序、又沒有空閑段的解有著相同的最大延遲 L 。 如果解中既沒有逆序、又沒有空閑段，那么相同最終期限的區(qū)間只有在次序上可能不同。而這些區(qū)間的最大延遲只和最后一個(gè) 區(qū)間的右端點(diǎn)坐標(biāo)有關(guān)，區(qū)間的次序卻并不影響最后一個(gè)區(qū)間的右端點(diǎn)坐標(biāo)，所以最大延遲始終相同。證畢。 命題 既沒有逆序、又沒有空閑段的解是最優(yōu)解。 根據(jù)命題 ，存在一個(gè)沒有空閑段的最優(yōu)解。假設(shè)某最優(yōu)解中相鄰的某兩區(qū)間 i 、 1?i 為逆序關(guān)系，即有 1?? ii dd 。設(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 。設(shè)兩區(qū)間在交換前后的延遲分別為 il 、 1?il 、 il? 、 1??il 。 因?yàn)?? ? ? ?1111111111 ,m a x,m a x?????????? ????????????????????????iiiiiiiiiiiiiii lllllllff ddllff ，所以il 、 1?il 不優(yōu)于 il? 、 1??il 。因此一個(gè)存在逆序的解交換相鄰的逆序項(xiàng)可以使之更優(yōu)，只要將一個(gè)有逆序的解不斷進(jìn)行上述操作后都能成為一個(gè)無逆序的解。證畢。 綜上所述，該算法成功構(gòu)造了一個(gè)最優(yōu)解。 實(shí)現(xiàn)： 按算法直接模擬。時(shí)間復(fù)雜度：排序 ? ?nnO log +掃描 ??nO = ? ?nnO log 。 一般在區(qū)間位置可變時(shí)，最優(yōu)解中各區(qū)間位置常常是按照最終期限排序，交換最終期限互為逆序的區(qū)間總能使結(jié)果更優(yōu)。當(dāng)然區(qū)間帶權(quán)時(shí)，要另外考慮。 例題 ： CTSC 2022 DAY2 pendant 題目大意： 有 ? ?202200?NN 粒綴珠 ，每粒綴珠有兩個(gè)參數(shù)：掛鉤的最大承受重量 iC 和本身重量 iW 。將綴 珠經(jīng)掛鉤連接后掛起形成掛墜，要求每粒綴珠下方的綴珠重量之和不能超過它掛鉤的最大承受重量。問掛墜最多能由多少個(gè) 綴珠組成，并求出滿足綴珠數(shù)量最多時(shí)掛墜質(zhì)量的最小值。 分析： 把每粒綴珠看作一個(gè)長(zhǎng)度為 iW 的區(qū)間，這些區(qū)間的位置是可變的。則問題轉(zhuǎn)化為：選出最多的區(qū)間，并將它們不互相重疊地放置在 ),0[ ?? 上，使得左端點(diǎn) 12 坐標(biāo)不能超過 iC 。在保證區(qū)間數(shù)量最大時(shí)，需求出最大右端點(diǎn)坐標(biāo)的最小值。 根據(jù)原 問題，容易證明下面這個(gè)結(jié)論：顯然必有一個(gè)最有解，它的區(qū)間按最后期限 ii CW? 排序，連續(xù)地放置在 ),0[ ?? 上。（證明和原問題的證明方法類似）在這個(gè)結(jié)論的基礎(chǔ)上，可以得出以下兩種算法。 算法 1： 容易想到一個(gè) ? ?2NO 的動(dòng)態(tài)規(guī)劃。將區(qū)間按 ii CW? 的值從小到大排序，設(shè)? ?jif , 為前 i 個(gè)區(qū)間 ，選取了 j 個(gè)區(qū)間后，最大右端點(diǎn)坐標(biāo)的最小值。則對(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 。狀態(tài)數(shù)為 ? ?2NO ，狀態(tài)轉(zhuǎn)移時(shí)間為??1O ，故時(shí)間復(fù)雜度為 ? ?2NO 。然而僅僅 ? ?2NO 是不夠的，還需要優(yōu)化。 優(yōu)化： 設(shè) ? ? ? ? ? ?1, ??? jifjifjig ,顯然 i 不變時(shí)， ? ?jig, 隨著 j 的增大而呈單調(diào)遞增（如果 ? ? ? ?1, ?? jigjig ,那么 ? ?1, ?jif 肯定不是最大右端點(diǎn)坐標(biāo)的最 小值）。故每次從 ??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 。 時(shí)間復(fù)雜度： 用一棵平衡二叉樹維護(hù) ??ig ，則從 ??ig 遞推 ? ?1?ig 的時(shí)間復(fù)雜度為 ? ?NOlog ， 13 所以總時(shí)間復(fù)雜度為：排序 ? ?NNO log + ??ig 的維護(hù) ? ? ? ?NONO log? = ? ?NNO log 。 該算法要用到平衡二叉樹，編程復(fù)雜度較大。其實(shí)仔細(xì)分析算法 1，并加以改進(jìn)，就可以得到一個(gè)貪心的算法。 算法 2： 維護(hù)一個(gè)按 ii CW? 排序的有序表，初始為空。將所有區(qū)間按長(zhǎng)度 iW 從小到大排序，依次處理。處理某個(gè)區(qū)間時(shí)，若它能夠放入有序表，則選擇該區(qū)間并放入表中， 否則不選擇。最后的表即是要求的狀態(tài)。 實(shí)現(xiàn)： 算法的瓶頸在有序表的維護(hù)上。如果直接模擬該表的所有操作，時(shí)間復(fù)雜度是 ? ?2NO 。用線段樹來維護(hù)該表，可以在 ? ?NOlog 的時(shí)間里完成每個(gè)區(qū)間的取舍及插入操作（這些操作并不是非常容易實(shí)現(xiàn)，但與論文主題無關(guān)，這里不再細(xì)寫）。因此，總時(shí)間復(fù)雜度為 ? ?NNO log 。 例題 ： Europe Southeastern 2022 Problem D 題目大意： 一家銀行收到了 ? ?100000 ?? NN 個(gè)貸款申請(qǐng)，每個(gè)貸款都最晚要在? ?100000 ?? ii dd 時(shí)完成，利潤(rùn)為 ip 。每個(gè)貸款需要一個(gè)單位時(shí)間處理，銀行在同一時(shí)間內(nèi)最多可以接受 ? ?1000 ?? LL 個(gè)貸款。求如何安排才能獲得最大利潤(rùn)。 分析： 將每個(gè) 貸款申請(qǐng)看作一個(gè)單位長(zhǎng)度、位置可變且?guī)?quán)的區(qū)間，則題目轉(zhuǎn)化為選出一些區(qū)間，將它們 不互相重疊地 放在 L 個(gè)資源 ),0[ ?? 上，使利潤(rùn)最大，且區(qū) 14 間的左端點(diǎn)不得超過 id 。可以用與例題 算法 2類似的 貪心算法解決該問題。 算法： 將這些區(qū)間按照權(quán)值從大到小排序，順序處理每個(gè)區(qū)間。設(shè) ? ?iNi dD ??? 1max。由于區(qū)間都是單位長(zhǎng)度的，我們可以用一維數(shù)組 ??? ?Diis ??1 來記錄當(dāng)前的情況，表示 ? ?1, ?ii 被覆蓋次數(shù)， 根據(jù)題意有 ?? Lis ??0 。處理第 i 個(gè)區(qū)間時(shí)，若可以選擇該區(qū)間（即 ? ? Lisdi i ???? ,0 ），則將該區(qū)間放置到一個(gè) i 最大的一個(gè)位置，即??? ?Lisiidi ??? |max0 ，否則就不選擇該區(qū)間。 處理每個(gè)區(qū)間時(shí)，若直接模擬，時(shí)間復(fù)雜度是 ? ?NDO ，最好還是做適當(dāng)優(yōu)化。 優(yōu)化 1： 若用一棵線段樹來維護(hù)數(shù)組 ??is ，可以在 ? ?DOlog 的時(shí)間里處理每個(gè)區(qū)間?？倳r(shí)間復(fù)雜度為：排序 ? ?NNO log +處理每個(gè)區(qū)間 ? ? ? ?DONO log? = ? ?? ?NDNO log 。 優(yōu)化 2： 每次 ??? ?0?iis 的值增加后，若 ?? Lis ? ，則將之所屬集合與前面的 ? ?1?is 所屬集合合并成一個(gè)新集合。處理第 i 個(gè)區(qū)間時(shí)，它選擇的位置必是 ??ids 所在集合中的最前面的元素，（若最前面的元素是 ??0s 且 ?? Ls ?0 ，則表示該區(qū)間不能被選擇）。如果我們用并查集來實(shí)現(xiàn)集合的各種操作，維護(hù)它的時(shí)間復(fù)雜度可近似地看作? ?DNO ? 。 總 時(shí) 間 復(fù) 雜 度 ： 排 序 ? ?NNO log + 處 理 每 個(gè) 區(qū) 間? ?DNO ? = ? ?NNDO log? 。 第 1種優(yōu)化由于用到了線段樹，不論在空間上還是在時(shí)間上都有著巨大的系 15 數(shù)；而第 2種優(yōu)化用到的空間非常小，且在時(shí)間效率和編程復(fù)雜度兩方面都比第1種好很多。 有 n 個(gè)區(qū)間，選擇盡量少的區(qū)間，使得這些區(qū)間完全覆蓋某線段 ? ?ts, 。 算法： 將所有區(qū)間按左端點(diǎn)坐標(biāo)從小到大排序，順序處理每個(gè)區(qū)間。每次選擇覆蓋點(diǎn) s 的區(qū)間 中右端點(diǎn)坐標(biāo)最大的一個(gè)，并將 s 更新為該區(qū)間的右端點(diǎn)坐標(biāo)，直到選擇的區(qū)間已包含 t 。 證明： 顯然，該算法最后選出來的區(qū)間 完全覆蓋 ? ?ts, ，下面證明所選出 區(qū)間的數(shù)量是最少的。 設(shè) if 為該算法所接受的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)， ig 為某最優(yōu)解中第i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)。 命題 當(dāng) 1?i 時(shí)：該算法所接受的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo) if ≥某最優(yōu)解中的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo) ig 。 該命題可以運(yùn)用數(shù)學(xué)歸納法來證明。對(duì)于 1?i ，命題顯然為真，因?yàn)樗惴ǖ谝粋€(gè)選擇的區(qū)間是能覆蓋點(diǎn) s 的區(qū)間中右端點(diǎn)坐標(biāo)最大的那個(gè)。令 1?i ，假定論斷對(duì) 1?i 為真，即 11 ?? ? ii gf ，最優(yōu)解中選的第 i 個(gè)區(qū)間的右端點(diǎn)坐標(biāo)為 ig ,設(shè)它的左端點(diǎn)坐標(biāo)為 ib 。由于該區(qū)間覆蓋 1?ig ，即 iii ggb ?? ?1 。當(dāng) 1?? ii fg 時(shí)，由于ii ff ??1 ，有 ii fg? ；當(dāng) 1?? ii fg 時(shí)，有 iiii gfgb ??? ?? 11 ，此時(shí)最優(yōu)解所選擇的區(qū)間覆蓋點(diǎn) 1?if ,又算法選擇的第 i 個(gè)區(qū)間是右端點(diǎn)坐標(biāo)最大的那個(gè)，故 ii gf? 。證畢。 16 設(shè)該算法 選出了 k 個(gè)區(qū)間，而最優(yōu)解選出了 m 個(gè)區(qū)間。 命題 最優(yōu)解選出的區(qū)間數(shù)量 m =該算法選出的區(qū)間數(shù)量 k 。 假設(shè) km? ，根據(jù)命題 ，有 mm gf ? 。根據(jù)該算法， tfg mm ?? ，因此該最優(yōu) 解不可能覆蓋 t ，產(chǎn)生矛盾。所以 km? ,又因?yàn)?m 是最優(yōu)解中選出區(qū)間個(gè)數(shù)，所以 km? 。 綜上所述，算法選出的區(qū)間是最優(yōu)解。 實(shí)現(xiàn)： 選擇區(qū)間可以通過線性掃描來實(shí)現(xiàn)。時(shí)間復(fù)雜度：排序 ? ?nnO log +掃描??nO = ? ?nnO log 。 例題 4： ACM/ICPC Regional Warmup Contest 2022 Problem E 題目大意： 有一塊草坪，長(zhǎng)為 l ，寬為 w ，在它的中心線的位置處裝有 ? ?10000?nn 個(gè)點(diǎn)狀的噴水裝置。每個(gè)噴水裝置 i 噴水的效果是以它為中心半徑為 ir 的圓都被潤(rùn)濕。請(qǐng)選擇盡量少的噴水裝置，把整個(gè)草坪全 部潤(rùn)濕。如圖所示： 17 分析： 顯然覆蓋整個(gè)草坪的充要條件是要能覆蓋上邊界。將每個(gè)噴水設(shè)置能覆蓋的一段上邊界看成一個(gè)區(qū)間，轉(zhuǎn)化后的問題就是原問題。 、覆蓋問題 若區(qū)間帶權(quán)，如何解決調(diào)度、覆蓋一類問題呢？這時(shí)，剛才一直用的貪心算法已經(jīng)不再普遍適用，大部分情況下，只能用更一般性的方法 —— 動(dòng)態(tài)規(guī)劃。 例題 ： Europe Northeastern Europe 2022 Problem J 題目大意： 有 ? ?1000?NN 只可愛的小海龜在賽跑。詢問每只小海龜它是第幾名，它會(huì)回答你兩個(gè)數(shù)： iiba, ，分別表示在它前面的小海龜數(shù)和在它后面的小海龜數(shù)。接著你發(fā)現(xiàn)其中有些小海龜對(duì)你撒了謊，因?yàn)楦鶕?jù)他們的說法你根本沒法給他們排隊(duì)！但是你是善良的，你不希望有很多小海龜在撒謊，想找出最少有哪幾只小海龜在撒謊。（注意：小海龜?shù)?名次可能是并列的?。? 分析： 若一只海龜說了真話，那么該海龜?shù)奈恢靡欢ㄊ窃趨^(qū)間 ? ?ii bNa ?? ,1 上。若有 K 只海龜選擇了相同的區(qū)間 ? ?ii bNa ?? ,1 ，則根據(jù)并列關(guān)系，該區(qū)間最多能同時(shí)擁有 ? ?KbaN ii ,m in ?? 只海龜?？梢杂?jì)算出每個(gè)區(qū)間最多能有多少只海龜，把數(shù)值看做區(qū)間的“權(quán)”。則問題轉(zhuǎn)化為，在一些帶權(quán)區(qū)間中，選出權(quán)和最大的區(qū)間，使它們之間不能互相重疊。 算法： 算出每個(gè)出現(xiàn)過的區(qū)間的 “權(quán) ” ??iv ，接下來的算法就是動(dòng)態(tài)規(guī)劃了。先按 18 右端點(diǎn)坐標(biāo)從小到大排序，令 ??ip 為在區(qū)間 i 左邊的且與之無公共點(diǎn)的最大區(qū)間編號(hào)，設(shè)狀態(tài) ??if 為在前 i 個(gè)區(qū)間中可選出區(qū)間的最大權(quán)和，則狀態(tài)轉(zhuǎn)移方程為? ? ? ? ? ?? ? ? ?? ?ivipfifif ??? ,1m a x ，說真話海龜?shù)淖畲髷?shù)量就是最后一個(gè)區(qū)間的 f值。 實(shí)現(xiàn)： 由于上述所有操作的排序關(guān)鍵字都在 N,...,1,0 中，所以可以使用時(shí)間復(fù)雜度為 ? ?NO 的基數(shù)排序，其它各操作也均能在 ? ?NO 時(shí)間內(nèi)