1、關于貪心法常州中學【摘要】每一個參加信息學競賽的選手都無法否認貪心法這一的重要性。當遇到一些比較棘手看起來很復雜的時候，手足無措的往往選擇貪心法搪塞一陣；而很多，經過一系列的轉化和變換，卻又讓人看到了貪心的。本文分成了兩個部分。第一部分是講貪心有力。很多人追求的是完美的算法，而不愿意選擇貪心，因為那可能只能拿一部分的分但也許事實并非如此？第二部分是講貪心有理。很多人不重視貪心法，所以很多時候無法事實上很多時候，貪心才是標準算法。【關鍵字】貪心理論證明貪心技巧綜合貪心【引言】貪心是每一次選擇一個局部最優策略進行實施，而不去考慮對今后的影響。一般來說它實現比較容易，時間復雜度也比較低，但是貪心未必

2、能夠得到最優解，并非是一個很“安全”的方法。但是貪心確實是一個適用范圍非常廣應該怎么用？怎么用才能達到最好的效果呢？段，這一點是很顯然的。那么貪心作者也說不清楚。需要明確的只是一點：貪心不會是一個算法，而只是一種。貪心有各種各樣的方法，到底怎么貪才好，需要自己的理解和領悟。因此本文并沒有過多地講述貪心的一般做法 希望大家能夠進一步地感知貪心法的那一片天地。，而是通過一些經典的例題【貪心有力】同樣高、同樣重、同樣聰明甚至擁有同樣性格同樣閱歷的人，未必會使用同一種貪心。YY的確，貪心是不是有用，還是要看怎么用。比如說，來看看一些例子：穿越磁場（CROSS）探險機器人在 Samuel 星球上尋找一塊

3、奇特的礦石，然而此時它陷入了一片神秘的磁場區域，動彈不得。探險空間站立刻掃描了這片區域，繪制出該區域的磁場分布平面圖。這片區域中分布了N 個磁場，每個磁場呈正方形，且邊與坐標軸平行。例如下圖中，存在 3 個磁場，白點表示機器人的位置，黑點表示礦石的位置：YXO科學家們分析平面圖，進一步發現：這些磁場為大小不一的正方形，可能相交，甚至覆蓋，但是它們的邊緣不會重合，頂點也不會重合。例如下面的兩種情形是不會出現的：科學家們給探險機器人啟動了磁力罩，這樣它就可以在磁場中穿越了。初始時，探險機器人和所有礦石都不在任何磁場的邊緣。由于技術限制，在穿越過程中機器人只能夠水平或垂直移動，且不能夠沿著磁場的邊緣

4、行動。由于磁力罩的能量有限，科學家們希望探險機器人穿越盡量少的磁場邊緣采集到這塊礦石。例如上圖中，探險機器人最少需要穿越兩次磁場邊緣。現在小聯請你編寫程序，幫助科學家們設計探險機器人的路線，統計探險機器人最少需要穿越多少次磁場邊緣。這道題的正確算法應該是先離散化然后再寬搜求解，這顯然是比較繁瑣的一件事情，差不多沒有 100 行是很難搞定的。但是如果貪心呢？也許比較奇怪，這種題目還能貪心么？事情就是這樣。思考：稍微了解一點點拓撲學的知識，應該知道對于這個問題，視矩形的大小甚至外形，只要記住相對的關系就可以了。可以無如果能夠想到這一點，配合要求，很容易想到一個著名的定理：封閉圖形的某一點與圖形外的

5、某一點的連線必然至少與圖形的邊相交 1 次。于都豁然開朗起來。考慮這個算法：只要窮舉每一個矩形，判斷起點A 和終點B 是否在矩形內。如果 A 和B 都在或都不在矩形內，那么理論上來講A 到 B 就不需要經過任何邊（僅考慮當前矩形的情況，下同）；如果 A和 B 有一個在矩形內，一個不在矩形內，那么從理論上來講 A 到 B 就恰好需要經過 1 條邊就可以了。然后就可以從理論上計算出最少要經過幾條邊。雖然這是下限，但是是不難想到的。會發現在絕大多數的情況下，正確的就是下限。這事實上，本題如果用這種方法來做，只要二十多行就可以了。這種算法，只錯了一個點。矩陣（matrix）曾經使用給定一個矩陣（即矩陣

6、中的元素僅為或），每次操作可以選擇某一行或某一列，將其中的全部刪除。問最少必須進行多少次操作，才可以將矩陣中所有的全部刪除。這是一道典型的二分圖匹配，但是也是可以用貪心來解決。這里提供了許多種貪心的方法：1.因為每一個 1 都是要被刪除的，所以考慮每一個 1 所在行和所在列。哪個包含的 1 多就刪除哪個。直到刪光為止。考慮每一行，哪一個包含的 1 多就刪除哪個。一直到所有的 1 都刪光為止。考慮如果有某一行或者某一列只有一個 1，那么必然刪除那個 1 所在的列或者行（因為總是要刪除這個 1 的，如果單單地刪除這一行或者列，那么顯然是不太合算的）。這樣刪直至不存在某一行或者某一個只有一個 1。那

7、么剩下的只要一行一行地刪就可以了。2.3.以上是當時省選時我聽說的幾種算法。顯然第三種是比較好的貪心，它過了當時的所有點。前面兩種大概至多只能過五六個點左右。但是貪心大師就有一個很好的想法。他選擇的是綜合貪心的方法。所謂的綜合貪心，就是把多種的貪心方法聯合在一起，統統實現一遍，然后選出一個最優解，所以他雖然沒有想到第三種貪心方法，但是他還是拿了 90 分。這是我極力的一種，因為對于只要輸出一個最優解而言，如果能夠將多個貪心方法聯合在一起，就可以達到互補的效果，從而解決幾乎所有的反例。因此如果使用綜合貪心的話，那么最好能夠盡可能多地尋找各種各樣有可能正確的貪心方法，不斷地為自己增加獲勝砝碼。YY

8、貪心，無論是方法還是結果，向來都是多多益善的。Matrix給定一個 0-1 矩陣，可對其各行、各列中的“1”的個數進行統計。例如下面這個 34 的矩陣：其中各 行包含“1”的個數分別是 1,3,2;各列包含“1”的個數分別是 2,1,2,1。對于一個 0-1 矩陣，給定各行包含的“1”的個數r1,r2，rn，以及各列包含“1”的個數 c1，c2，cm。同時，指定一些矩陣中的一些元素必須為 0，題目保證每行，每列至多有一個必須為 0 的元素。你的任務是判斷是否存在滿足上述要求的 01 矩陣。也許貪心法都是叫matrix 的？：）反正的時候，我第一眼看到這道題，當即就沒有多想，一口咬定這就是貪心。

9、具體方法是這樣的：首先如果某一個格子已經確定是 0，那么我不妨忽略它，把它改成確定是 1即它所在行和所在列的 1 的個數都加上 1。如果原圖是可以達到的，我變換了這個圖之后，這個圖也是可以達到的（注意到這并不是充要條件，即如果這個圖可以達到，那么原圖未必可以達到）。然后我就得到了一個比較容易處理的圖：它不存在某一個格子必定是 0 的情況，而只是告訴了你某一行有多少個 1，某一列有多少個 1。這樣的話，那么我只要當前每一行多少個 1，然后一列一列地看過來。如果當前列有a 個 1，那么我就把所有行的 1 排序，然后從大到小排序。因為出現無解情況只可能是因為雖然行和列的 1 的總個數是一樣的，但是檢

10、查到某一列的時候，出現了比如說該列有 3 個 1，只剩下了 2 行，一行有 1 個 1，一行有 2 個 1 的情況。所以如果我將行排序的話，那么保證了可供選擇的行是最多的，所以如果能夠排成功的話，我一定能夠檢測到，即排法是最優的。因此我認為在這種情況下，算法是正確的。但是遺憾的是如果轉換后的圖是可以構造的，并不意味著原圖也是可以構造的；而如果轉換后的圖已經不能構造了，那么可以肯定原圖也是不能構造的。所以那一題我沒有全對，很多no 的情況，我都打了yes。只是錯了這種情況。然后大家都說這題是網絡流。當然網絡流也是沒有錯的，但是數據量過大了？我猜想，會不會這道題的標準算法就是貪心呢?學校的這道題拿

11、了滿分。他就是貪心做的，大體的方法和是一樣的，但是他沒有轉換模型，而是直接在原圖上貪心的。這樣的話已經確定的含0 的格子可能會對問題造成一定的困擾：因此他將這種格子做成了第二關鍵字進行排序，即當兩行擁有的 1 的個數相同的時候，優先考慮的是含 0 格更前的那一行（由題知不可能有兩行的含 0 格在相同的一列），這樣在以后安排的時候，也會有的空間可供選擇。這樣說似乎模糊了一點點，感覺這種方法是有點道理的，但是沒有沒有說這是正確的。如果能夠找到反例，歡迎和我聯系。至此想說明一點，當你對于某一個問題感到束手無策的時候，不妨使用貪心法。它也許并非是完美的算法（沒人命令你必須使用最完美的算法！），你不能證

12、明它是對的或者它根本就是錯的，但是這么多的事例給還是很有用的。的啟示是，它很多時候，你并不是缺少貪心的【貪心有理】，而是缺少貪心的勇氣。YY當你發現某一道題你根本就找不到一個真實可靠的算法而惶恐的時候，也許你只是漏了貪心。YY貪心法并非總是不完美的算法，事實上很多題目不得不選擇貪心。此時的貪心就是正確的，題：往往可以選擇漂亮地證明它。比如可以看下面這道多個關鍵字的排序(keys)時限：6s內存限制：10MB考慮一個有C 列的表格。為了簡單起見，表格中的元素均為小寫字母組成的字符串。表格 1表格 2表格 3給出了 sort（k）這么一個過程，它將會根據第 k 列的元素的進行大小排序，以一行為。這

13、個排序是穩定的，即如果有兩行在 k 列的元素大小相等，那么它們將會保持相對的位置不變。對于表格 1 使用 sort（2）過程，就得到了表格 2。對于這種操作的序列很感。這些操作將統統作用于一個表格，并且是嚴格地根據操作地序列順序進行的。例如對于表格 1，先 sort（2），再 sort（1），就得到了表格 3。Col. 1Col. 2Col. 3ApplegreensourAppleredstbananabrownrottenbananayellowstPeargreenstCol. 1Col. 2Col. 3bananaBrownrottenapplegreensourpeargreenst

14、appleredstbananayellowstCol. 1Col. 2Col. 3AppleRedStAppleGreenSourPearGreenstbananaYellowstbananaBrownrotten如果對于任意的表格，兩個操作序列都會有相同的效果，那么這兩個操作序列就被認為是相同的。比如說，sort（2）；sort（2）；sort（1）和 sort（2）； sort（1）是相同的。但是它們和 sort（1）；sort（2）是不同的，因為它們作用于表格 1 的時候，會有不同的效果。你的任務是，給你一串操作序列，請你找到最短的與它相同的序列，輸出它的長度。（1 C 1 000 0

15、00，1 N 3 000 000）這是CEOI2005 的一道題，我和曾經認真地過此題應該如何解決。也許動態規劃，也許并查集，也許網絡流，但是當仔細地看到它的數據規模的時候，才清晰地認識到此題必然是貪心，至少有一種比較簡易的方法。現在我可以給你一點點的提示了這個小定理：曾經花了很大的功夫用數學歸納法證明如 果 某一 個操 作序 列 含有 局部 的重 復的 話 （ 諸 如 sort(a);sort(b); sort(a);sort(b)），那么可以將重復部分刪去，因為這些部分是沒用的。這的確是一個不錯的啟發。但是這個如何實現呢？ 序列長最大為3000000，時限為 6s，這就迫使用諸如 O（n）

16、或者 O（nlogn）的算法。那么怎么在O（nlogn）的時間內判重呢？于是我當時又思考了很久，似乎這個不可能？！也許是算法錯了。我又重新思考這個問題，能不能將這個問題轉換成為別的模型呢？于是到可以把一系列的操作看作是一種多重的排序，那么起關鍵作用的顯然是最后一次的排序了。那么前面的排序會不會產生一定的影響呢？看到題目中說這是一種穩定的排序，所以知道：當且僅當最后一次排序之后，兩個數是相同的，那么它們的相對位置才不是最后決定的（不妨稱這種情況為不能確定），否則它們的相對位置均由最后的一次操作決定。那么如果兩數相同，它們的相對位置是由什么決定的呢？這是穩定的排序。所以想到它們的相對位置必然是由之

17、前的操作決定的。如果在倒數第二次操作的時候，它們所在行的相對位置不是不能確定，那么它們的相對位置就將保持到最后；如果它們所在行的相對位置還是不能確定，那么可以繼續看倒數第三次操作。這樣就很清晰地聯想到了按第一第二關鍵字排序。事實上，這么一個操作序列的本質就是按照第一第二關鍵字排序。進一步想，因為如果某一次排序，某一個關鍵字既是第一關鍵字，又是第 x關鍵字，那么后一個關鍵字顯然是沒有意義的，因為當且僅當第一關鍵字相同的時候才會考慮后面的關鍵字。所以某一個操作序列能夠被縮短當且僅當該操作序列的有相同的操作。而且，如果要縮短操作序列，只需要去掉所有多余的重復操作，保留最后一個就行了。然后就發現問題就

18、這樣解決了。雖然規模達到了 3000000，但是開一個 hash表，只要O（n）的時間就可以完成。通過這個例題發現，貪心也是很需要技巧的。要知道如何貪心，不僅要牢牢地抓住問題的本質，而且還要學會理性地分析，從各個角度觀察和思考，找到最切合實際的方法。當然這只是一道比較簡單，但是一旦陷入思維定式（比如剛開始就想錯了方向），就會感到無從下手。我認為想要好好貪心，不僅要敢于下手，還要敢于放手，學會換角度思考。當然做別的事情也是如此，只是我認為在貪心方面尤為重要罷了。只有一個學識淵博，胸襟寬闊，才思敏捷，敢于創新，可能真真正正地學好貪心。突破，能屈能伸YY的售票處時限：0.5s內存限制：64MB一個售

19、票處賣演唱會的門票。但是它總是賣長度固定的連續座位的票而不再是單單地賣。售票處受到了一堆的訂單。一個訂單僅用在需要訂的連續座位中的最小的座位號（即一個數字）表示。售票處可能不能滿足所有的訂單的需求。并且，如果如果只是按照訂單上安排地那樣去賣票，那么可能會有大批的座位是空著的。因此，售票處有以下的安排和定價策略。如果一個訂單被采納并且分配給買方的座位恰為訂單所要求的連續座位，那么買方將付 2 元（這種票不妨被稱為原定票）。如果一個訂單被采納但是分配給買方的連續座位并非是訂單所要求的連續座位（只要有一個座位不同就視作不同），那么買方將付 1 元（這種票成為改訂票）。如果一個訂單沒有被采納，那么顯然

20、就沒錢可賺。：）作為一個商人，你顯然想賺最多的錢。那么請輸出最多能賺任意方案。，并輸出此題也是很有意思的一道題，怎么做呢？初看我不知道，因為如果用動態規劃狀態量比較大，沒法來做，所以不管貪不貪心，首先都要看清題意，仔細分析。于是就應該有貪心的。首先想到怎么說都是按照顧客的意思辦比較賺（畢竟顧客就是上帝么：），因為某個地方要放一個原定票，但是卻有兩個改訂票和這塊區域有交集（至多只有兩個改訂票），那么我如果放原定票是更加合算一點點（因為不僅得到的錢一樣多，而且占的空間小了）。所以就知道了，放盡可能多的原定票是最優的。那么cmc 在這個基礎之上就有了一個簡單的動態規劃，比如說用optI表示i 個格子

21、里最多能夠有多少改訂票。那么推的話就比較容易了（因為證明了一定要盡可能多地放原定票，那么其實前 i 個格子里要買多少張原定票是已經決定了）。但是CEOI 方面給出的一個標準算法卻是將貪心進行到底的一個表現。它是首先從頭開始，能放原定票就放原定票，然后再進一步地調整。我認為這樣的貪心是沒有多少意義的。貪心在很大程度上只是一種，一種，是到達目的地的捷徑，理應是為了結果而貪心，卻不必要純粹地為了貪心而貪心。如果得到了“放盡可能多的原定票是最優的”這個結論就可以比較快速地將問題解決，那么也沒有必要繼續下去。事實上，在賽場上，會有多少人能夠把這道題的版解答方案想出來呢？將貪心用于點點滴滴，我猜想大多數人

22、使用的還是DP 的方法吧。因此要幫助更好地解題，而不是追求一個虛無飄渺的完整貪心的過程。當你已經可以把蛇身畫出來的時候，就不用再去想要不要添只腳了。YYMqueue的n 頭（1=nmax(Ya+Xa+Xb, YaYbXb)可轉換為：min(Xa,Yb)min(Xb,Ya)這也是不難理解的。因為兩頭奶牛一起擠奶的話，用時其實是 Xa+Xb+Ya+Yb-公共用時。而公共用時min(Xa,Yb)（即Y 先擠奶）或者 min(Xb,Ya)（X 先擠奶）那么兩者中選大即可。就此掌握了判斷交換奶牛順序是否更優的方法。因此剩下變得很簡單了。列。可以將這種方法變成關鍵字進行排序，最后所得的序列即為最終序不斷地

23、調整結果，通過貪心地獲得局部的較優解不斷近最優解，也是非常重要的貪心。YYCow AcrobatsFarmer John 養了N(1=N=50,000)頭牛，她們已經按 1N 依次編上了號。 FJ 所不知道的是，他的所有牛都夢想著從農場逃走，去參加馬戲團的演出。可奶牛們很快發現她們那笨拙的蹄子根本無法在鋼絲或晃動的的秋千上站穩（她們還嘗試過把自己裝在里發射出去，但可想而知，結果是悲慘的）。最終，她們決定練種最簡單的雜技：把所有牛都摞在一起，比如說，第一頭牛站在第二頭的身上，同時第二頭牛又站在第三頭牛的身上.最果然沒什么創造力）的是第N 頭牛。（牛每頭牛都有自己的體重以及力量，為i 的奶牛的體重為W_i(1=W_i=10,000)，力量為S_i(1=S_i=1,000,000,000)。當某頭牛身上站著另一些牛時它就會在一定程度上被壓扁，不妨把它被壓扁的程度叫做它的壓扁指數。對于任意的牛，壓扁指數等