【正文】 格作為射擊格即可 上面的貪心方法非常高效： 時(shí)間復(fù)雜度為 O(R?C)，如果在程序中使用堆優(yōu)化，時(shí)間復(fù)雜度將降為 O(R?log2C)?？臻g復(fù)雜度是線性的，而且非常容易實(shí)現(xiàn)。 現(xiàn)在關(guān)鍵的問題就是 —— 如何證明它的正確性？ 證明： 用 h[i]表示第 i行的白格數(shù)。如果最開始的時(shí)候： ? ① min{h[i]}=0：第 i行已經(jīng)沒有辦法找到可作為射擊格的白格，那么問題只能無(wú)解。 ? ② min{h[i]}=1：那么第 i行的這一個(gè)白格必須要作為射擊格，否則將因第 i行沒有射擊格而造成問題無(wú)解。 ? ③ min{h[i]}≥2 ：那么在這一行任選一個(gè)白格 ,頂多只會(huì)造成剩余行中有一行 h值為 1,再處理那一行，最多也只會(huì)再造成剩余行中有一行 h值為 1，如此往復(fù) ,將保持 h值為 1的行數(shù)不超過 1行，最后最壞的情況也是造成最后一行的 h值為 1,繼續(xù)下去所有行就都已選取了射擊格了。 ? 因此，如果原問題有解，該貪心方法一定能找到一種正確的方案。由此可以證明，此貪心方法是正確的。確定貪心標(biāo)準(zhǔn)。 貪心的經(jīng)典應(yīng)用 （一）、三個(gè)區(qū)間上的問題 選擇不相交區(qū)間問題 區(qū)間選點(diǎn)問題 區(qū)間覆蓋問題 （二）、兩個(gè)調(diào)度問題 流水作業(yè)調(diào)度問題 帶限期和罰款的單位時(shí)間任務(wù)調(diào)度 （三） Huffman編碼 （四） 最優(yōu)合并問題 選擇不相交區(qū)間問題 ? 給定 n個(gè)開區(qū)間 (ai, bi)，選擇盡量多個(gè)區(qū)間，使得這些區(qū)間兩兩沒有公共點(diǎn)。 【 算法實(shí)現(xiàn) 】 首先按照 b1=b2=… =bn的順序排序，依次考慮各個(gè)活動(dòng)，如果沒有和已經(jīng)選擇的活動(dòng)沖突，就選；否則就不選。 貪心策略：取第一個(gè)區(qū)間； 【 正確性 】 ： 如果不選 b1，假設(shè)第一個(gè)選擇的是 bi，則如果 bi和 b1不交叉則多選一個(gè) b1更劃算；如果交叉則把 bi換成 b1不影響后續(xù)選擇。 例題 5：活動(dòng)安排 ? 設(shè)有 n個(gè)活動(dòng)的集合 E={1,2,..,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng) i都有一個(gè)要求使用該資源的起始時(shí)間 si和一個(gè)結(jié)束時(shí)間 fi，且 sifi。如果選擇了活動(dòng) i，則它在半開時(shí)間區(qū)間 [si,fi)內(nèi)占用資源。若區(qū)間 [si,fi)與區(qū)間 [sj,fj)不相交，則稱活動(dòng) i與活動(dòng) j是相容的。也就是說(shuō)，當(dāng) fi=sj或 fj=si時(shí)，活動(dòng) i與活動(dòng) j相容。選擇出由互相兼容的活動(dòng)組成的最大集合。 區(qū)間選點(diǎn)問題 ? 給定 n個(gè)閉區(qū)間 [ai, bi]，在數(shù)軸上選盡量少的點(diǎn)，使得每個(gè)區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）。 【 算法 】 ： 首先按照 b1=b2=… =bn排序。每次標(biāo)記當(dāng)前區(qū)間的右端點(diǎn) X，并右移當(dāng)前區(qū)間指針，直到當(dāng)前區(qū)間不包含 X，再重復(fù)上述操作。 貪心策略：取最后一個(gè)。 例題 6：種樹（ NOIP模擬試題） ? 一條街的一邊有幾座房子。因?yàn)榄h(huán)保原因居民想要在路邊種些樹。路邊的地區(qū)被分割成塊，并被編號(hào)為 1..n。每個(gè)塊大小為一個(gè)單位尺寸并最多可種一棵樹。每個(gè)居民想在門前種些樹并指定了三個(gè)號(hào)碼 b,e,t。這三個(gè)數(shù)表示該居民想在 b和 e之間最少種 t棵樹。當(dāng)然， b=e,居民必須保證在指定地區(qū)不能種多于地區(qū)被分割成塊數(shù)的樹，即要求 t=eb+1。允許居民想種樹的各自區(qū)域可以交叉。出于資金短缺的原因 ,環(huán)保部門請(qǐng)你求出能夠滿足所有居民的要求 ,需要種樹的最少數(shù)量。 樣例輸入 : 9 4 1 4 2 4 6 2 8 9 2 3 5 2 樣例輸出： 5 區(qū)間覆蓋問題 ? 給 n個(gè)閉區(qū)間 [ai,bi]，選擇盡量少的區(qū)間覆蓋一條指定線段 [s,t]。 ? 本題的突破口仍然是區(qū)間包含和排序掃描，不過先要進(jìn)行一次預(yù)處理。每個(gè)區(qū)間在 [s,t]外的部分都應(yīng)該預(yù)先被切掉，因?yàn)樗鼈兊拇嬖谑呛翢o(wú)意義的。在預(yù)處理后，在相互包含的情況下，小區(qū)間顯然不應(yīng)該考慮。 ? 把各區(qū)間按照 a從小到大排序，若 a相同，則 b從大到小排序（自動(dòng)處理掉區(qū)間包含）。注意：若區(qū)間 1的起點(diǎn)大于 s，則無(wú)解（因?yàn)槠渌麉^(qū)間的起點(diǎn)更大，不可能覆蓋到 s點(diǎn)），否則選擇起點(diǎn)在 s的最長(zhǎng)區(qū)間 [ai,bi]后，新的起點(diǎn)應(yīng)該設(shè)置為 bi，并且忽略所有區(qū)間在 bi之前的部分，就像預(yù)處理一樣。雖然貪心策略比上題復(fù)雜，但是仍然只需要一次掃描，如下圖， s為當(dāng)前有效起點(diǎn)（此前部分已被覆蓋），則應(yīng)該選擇區(qū)間 2。 貪心思想：在某個(gè)時(shí)刻 s，找一個(gè)滿足 a[i]=s的 b[i]的最大值即可。 例題 7：區(qū)間（ SDOI2022） ? 現(xiàn)給定 n個(gè)閉區(qū)間 [ai,bi]， 1=i=n。這些區(qū)間的并可以表示為一些不相交的閉區(qū)間的并。你的任務(wù)就是在這些表示方式中找出包含最少區(qū)間的方案。你的輸出應(yīng)該按照區(qū)間的升序排列。這里如果說(shuō)兩個(gè)區(qū)間 [a, b]和 [c, d]是按照升序排列的，那么我們有 ab=c=d。 任務(wù)：讀入這些區(qū)間，計(jì)算滿足給定條件的不相交閉區(qū)間，并把這些區(qū)間按照升序輸出。 練習(xí)試題：噴水裝置 ? 有一塊草坪，長(zhǎng)為 L，寬為 w； 在它的中心線上裝有 n個(gè)點(diǎn)狀的噴水裝置，效果是讓以它為中心半徑為 ri的圓被潤(rùn)濕，選擇盡量少的噴水裝置把整個(gè)草坪全部潤(rùn)濕。 流水作業(yè)調(diào)度問題 樣例 5 //作業(yè)個(gè)數(shù) 4 5 8 7 3 //每個(gè)作業(yè) M1機(jī)器上加工時(shí)間 6 2 1 4 9 //每個(gè)作業(yè) M2機(jī)器上加工時(shí)間 分析 帶限期和罰款的單位時(shí)間任務(wù)調(diào)度 7 2 4 1 4 6 4 3 60 50 30 20 10 70 40 貪心方法的推廣 ? 貪心與其它算法結(jié)合 – 搜索的最優(yōu)化剪枝（ 生日蛋糕） – 優(yōu)化動(dòng)態(tài)規(guī)劃（ Peter的快餐店） ? 貪心方法與解題策略 – 最優(yōu)方法不一定是最好方法 – 想不到最優(yōu)解法就用較優(yōu)解法 貪心與其它算法結(jié)合 例題 11： Peter的快餐店 （貪心與動(dòng)態(tài)規(guī)劃） Peter最近在 R市新開了一家快餐店。 該快餐店準(zhǔn)備推出一種套餐，每套由 A個(gè)漢堡、 B個(gè)薯?xiàng)l和 C個(gè)飲料組成。為了提高產(chǎn)量， Peter引進(jìn)了 N條生產(chǎn)線。所有生產(chǎn)線都可以生產(chǎn)漢堡、薯?xiàng)l和飲料，由于每條生產(chǎn)線一天能工作的時(shí)間是有限的、不同的，而漢堡、薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同，Peter需要知道，怎樣安排才能是一天中生產(chǎn)的套餐量最大。假設(shè)一天中漢堡、薯?xiàng)l和飲料的產(chǎn)量均不超過 100個(gè)，且生產(chǎn)線總數(shù)小于等于 10。 分析 ? 本題是一個(gè)非常典型的資源分配問題。由于每條生產(chǎn)線的生產(chǎn)是相互獨(dú)立，不互相影響的，所以此題可以以生產(chǎn)線為階段用動(dòng)態(tài)規(guī)劃求解。 ? 狀態(tài)表示： 用 p[i][j][k]表示前 i條生產(chǎn)線生產(chǎn) j個(gè)漢堡， k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。 ? 用 r[i][j][k]表示第 i條生產(chǎn)線生產(chǎn) j個(gè)漢堡， k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。 ? 狀態(tài)轉(zhuǎn)移方程 :p[i][j][k]=Max{p[i1][j1][k1]+r[i][jj1][kk1]} ? (0=j1=j,0=k1=k,且 (jj1)*p1+(kk1)*p2= 第 i條生產(chǎn)線的生產(chǎn)時(shí)間 ) ? 但這樣的算法是非常粗糙的，稍加分析可以發(fā)現(xiàn)，此算法的時(shí)間復(fù)雜度為 O(N*1004),當(dāng) N=10的時(shí)候，時(shí)間復(fù)雜度將達(dá)到 10*1004=109，這是根本無(wú)法承受的。 用貪心方法作預(yù)處理 ： ? 首先計(jì)算出一天生產(chǎn)套數(shù)的上限值： min{100 div A,100 div B,100 div C} ? 接著，用貪心方法計(jì)算出這 N條生產(chǎn)線可以生產(chǎn)的套數(shù)，并與上限比較，大于或等于則輸出上限值并退出，否則再調(diào)用動(dòng)態(tài)規(guī)劃。因?yàn)樨澬姆椒ǖ拇鷥r(jià)很低，這里甚至可以使用多次貪心標(biāo)準(zhǔn)不同的貪心方法，取其最大值。 ? 在運(yùn)行動(dòng)態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，將貪心思想充分融入到動(dòng)態(tài)規(guī)劃過程中，這樣以來(lái)，便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)束程序。 算法步驟： 貪心小結(jié) : ? 貪心作為一種解題思路，雖然有時(shí)無(wú)法證明它的正確性，但在無(wú)法找到其他算法的時(shí)候，不失為一種好方法。 ? 并且，貪心與其他算法的結(jié)合，可以對(duì)其他算法起到優(yōu)化作用。