NOI導(dǎo)刊-貪心與分治

貪心與分治長(zhǎng)沙市第一中學(xué)曹利國(guó)貪心方法按照當(dāng)前的狀態(tài)，選擇最好的決策，這就是貪心法。在實(shí)際的應(yīng)用中，人們往往不可能精確計(jì)算出怎樣才是最好的決策，只能憑借往常的經(jīng)驗(yàn)，保證每一步都是最好的選擇。在解題的過(guò)程中，這樣的算法一般是比較容易想到并且易于編程實(shí)現(xiàn)的。能夠使用貪心算法解決的問(wèn)題，必然是每次都進(jìn)行最優(yōu)的選擇，并且通過(guò)證明其得到的最后結(jié)果也是最優(yōu)的。反之，如果不能證明每次進(jìn)行最優(yōu)選擇后，最終會(huì)得到最優(yōu)的結(jié)果，就不能使用貪心算法。其實(shí)，大局部的問(wèn)題都是不能使用貪心算法的，簡(jiǎn)單的例子：現(xiàn)有10元、7元、2元、1元四種紙幣，使用的張數(shù)不限，需要用這四種紙幣湊成p元錢(qián)，怎樣用最少的張數(shù)到達(dá)此要求。此題我們很容易就想到了貪心的算法，即每次盡量選面值大的紙幣。但是，在p=14時(shí)，貪心算法的結(jié)果為14=10+2+2，而最優(yōu)結(jié)果為14=7+7，貪心顯然是不對(duì)的。然而，如果我們將其中的7元紙幣換成5元紙幣，貪心算法卻又是對(duì)的。這就需要我們用證明來(lái)判斷了。例題1罰款問(wèn)題 現(xiàn)有一臺(tái)機(jī)器以及n項(xiàng)要完成的工作，該機(jī)器每完成一項(xiàng)工作需要1的單位時(shí)間，而工作i如果沒(méi)有在t[i]的時(shí)間內(nèi)完成，將會(huì)受到c[i]的罰款。求怎樣安排工作的順序，使完成工作后總的罰款數(shù)最少。分析要使罰款最少，我們顯然應(yīng)盡量完成c[i]值較大的工作。此時(shí)，我們可以將工作按c[i]從大到小進(jìn)行排序，然后按照排好的順序依次對(duì)工作進(jìn)行安排，安排的規(guī)那么為：使處理工作i的時(shí)間既在t[i]之內(nèi)，又盡量靠后；如果t[i]之內(nèi)的時(shí)間都已經(jīng)排滿，就放棄處理此項(xiàng)工作。

證明假設(shè)按照上述方法得到的解不是最優(yōu)的，那么必然存在某個(gè)工作j應(yīng)當(dāng)安排到處理的過(guò)程中，卻沒(méi)有得到安排。假設(shè)我們要將該工作安排進(jìn)去，由于時(shí)間t[j]內(nèi)都已經(jīng)排滿，就必然需要將一個(gè)已安排的工作k與之替換，而c[k]>=c[j]，這樣替換顯然會(huì)增加罰款的數(shù)額。因此，除上述安排方法以外的安排方法都不會(huì)使罰款的數(shù)額減少，可得上述方法得到的結(jié)果是最優(yōu)的。例題2：INT〔整數(shù)區(qū)間〕

定義

一個(gè)整數(shù)區(qū)間[A，B]，A﹤B，是一個(gè)從A開(kāi)始，至B結(jié)束的連續(xù)整數(shù)的集合。任務(wù)是從文件中讀取區(qū)間的個(gè)數(shù)及其對(duì)它們的描述，找出滿足下述條件的所含元素個(gè)數(shù)最少的集合中元素的個(gè)數(shù)：對(duì)于每一個(gè)區(qū)間，都至少有兩個(gè)不同的整數(shù)屬于該集合。輸入：文本文件INT.IN的首行包括區(qū)間的數(shù)目N，1≦N≦10000。接下來(lái)的N行，每行包括兩個(gè)整數(shù)A，B，被一空格隔開(kāi)，0≦A≦B≦10000，它們是某一個(gè)區(qū)間的開(kāi)始值和結(jié)束值。輸出：最少元素?cái)?shù)目。例如輸入：436240247輸出：4分析此題“會(huì)場(chǎng)安排”問(wèn)題十分相似，可以用同樣的貪心方法：按照所有區(qū)間的結(jié)束位置排序，結(jié)束位置相同的項(xiàng)，開(kāi)始位置小的項(xiàng)在前。從區(qū)間1到區(qū)間n進(jìn)行循環(huán)，對(duì)于當(dāng)前區(qū)間，假設(shè)集合中的數(shù)不能覆蓋它，那么從區(qū)間末尾向前掃描，假設(shè)當(dāng)前數(shù)未在集合中出現(xiàn)，那么將該數(shù)參加集合，直至使集合能覆蓋該區(qū)間為止。例如：【0，1，2】【2，3，4】【3，4，5，6】【4，5，6，7】【】【2】【2,1】【2,1,4】【2,1,4,6】上述算法的指導(dǎo)思想是在某一區(qū)間中排列越靠后的數(shù)對(duì)以后區(qū)間的影響越大，即它在以后區(qū)間出現(xiàn)的可能性越大，但未經(jīng)嚴(yán)格數(shù)學(xué)證明

具體實(shí)現(xiàn)由于pascal規(guī)定的集合類型只有[0..255]，因此在實(shí)現(xiàn)時(shí)不能使用集合作數(shù)據(jù)結(jié)構(gòu)，用數(shù)組直接保存也不行，因?yàn)樵跀?shù)組中查找數(shù)據(jù)相當(dāng)費(fèi)時(shí)，注意到每個(gè)區(qū)間中的數(shù)大小不超過(guò)10000，可用一個(gè)下標(biāo)為[0..10000]的布爾型數(shù)組標(biāo)記該數(shù)是否出現(xiàn)過(guò)，從而解決這一問(wèn)題。例題3：零件分組某工廠生產(chǎn)一批棍狀零件，每個(gè)零件都有一定的長(zhǎng)度〔Li〕和重量〔Wi〕?，F(xiàn)在為了加工需要，要將它們分成假設(shè)干組，使每一組的零件都能排成一個(gè)長(zhǎng)度和重量都不下降〔假設(shè)i<j，那么Li<=Lj，Wi<=Wj〕的序列。請(qǐng)問(wèn)至少要分成幾組?輸入：第一行為一個(gè)整數(shù)N〔N<=1000〕，表示零件的個(gè)數(shù)。第二行有N對(duì)正整數(shù)，每對(duì)正整數(shù)表示這些零件的長(zhǎng)度和重量，長(zhǎng)度和重量均不超過(guò)10000。輸出：僅一行，即最少分成的組數(shù)。樣例〔STICK.IN〕58438239735STICK.OUT2例題4：乘船問(wèn)題〔ＨＮＣＯＩ〕 有N個(gè)人需要乘船，而每船最多只能載兩人，且必須同名或同姓。求最少需要多少條船。問(wèn)題分析看到這道題，很多人都會(huì)想到圖的數(shù)據(jù)結(jié)構(gòu)：將N個(gè)人看作無(wú)向圖的N個(gè)點(diǎn)，凡同名或同姓的人之間都連上邊。要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現(xiàn)在圖中就是要用最少的邊完成對(duì)所有頂點(diǎn)的覆蓋。這就正好對(duì)應(yīng)了圖論的典型問(wèn)題：求最小邊的覆蓋。所用的算法為“求任意圖最大匹配”的算法。分析使用“求任意圖最大匹配”的算法比較復(fù)雜(要用到擴(kuò)展交錯(cuò)樹(shù)，對(duì)花的收縮等等)，效率也不是很高。因此，我們必須尋找一個(gè)更簡(jiǎn)單高效的方法。 首先，由于圖中任兩個(gè)連通分量都是相對(duì)獨(dú)立的，也就是說(shuō)任一條匹配邊的兩頂點(diǎn)，都只屬于同一個(gè)連通分量。因此，我們可以對(duì)每個(gè)連通分量分別進(jìn)行處理，而不會(huì)影響最終的結(jié)果。同時(shí)，我們還可以對(duì)需要船只s的下限進(jìn)行估計(jì)：對(duì)于一個(gè)包含Pi個(gè)頂點(diǎn)的連通分量，其最小覆蓋邊數(shù)顯然為[Pi/2]。假設(shè)圖中共有L個(gè)連通分量，那么s=∑[Pi/2](1<=i<=L)。 然后，我們通過(guò)屢次嘗試，可得出一個(gè)猜測(cè)： 實(shí)際需要的覆蓋邊數(shù)完全等于我們求出的下限∑[Pi/2](1<=i<=L)。采用圖的數(shù)據(jù)結(jié)構(gòu)得出的算法為：每次輸出一條非橋的邊，并從圖中將邊的兩頂點(diǎn)刪去。此算法的時(shí)間復(fù)雜度為O(n3)?！矊ふ乙粭l非橋邊的復(fù)雜度為O(n2)，尋找覆蓋邊操作的復(fù)雜度為O(n)〕采用樹(shù)結(jié)構(gòu)解決見(jiàn)文檔例題５：通訊保衛(wèi)戰(zhàn)見(jiàn)文本例題６：猜數(shù)游戲猜數(shù)游戲是一個(gè)古老的智力游戲。一個(gè)游戲者A首先想出一個(gè)數(shù)x〔1xn〕，讓另一個(gè)游戲者B來(lái)猜