網(wǎng)上找的一些算法關(guān)于貪心法

1、關(guān)于貪心法常州高級(jí)中學(xué) 袁洋 貪心是每一次選擇一個(gè)局部最優(yōu)策略進(jìn)行實(shí)施，而不去考慮對(duì)今后的影響。一般來(lái)說(shuō)它實(shí)現(xiàn)比較容易，時(shí)間復(fù)雜度也比較低，遺憾的是貪心未必能夠得到最優(yōu)解，并非是一個(gè)很“安全”的方法。 但是貪心確實(shí)是一個(gè)適用范圍非常廣的手段，這一點(diǎn)是很顯然的。那么貪心應(yīng)該怎么用？怎么用才能達(dá)到最好的效果呢？ YY也說(shuō)不清楚。需要明確的只是一點(diǎn)：貪心不會(huì)是一個(gè)算法，而只是一種手段。貪心有各種各樣的方法，到底怎么貪才好，需要自己的理解和領(lǐng)悟。 因此我并不會(huì)過(guò)多地講述貪心的一般做法云云，而是通過(guò)一些經(jīng)典的例題希望大家能夠進(jìn)一步地感知貪心法的那一片天地?！疽浴控澬挠辛uestion: YY在第一次

2、參加計(jì)算機(jī)的培訓(xùn)的時(shí)候，一共有4道題目。他首先做了第一題，用了貪心法；然后做了第二題，還是貪心法；接著他做了第三題，繼續(xù)貪心法最后是第四題，果然，又是貪心法。那么，為什么YY如此頻繁地使用貪心法呢？！思考：顯然，問(wèn)題不可能都是用貪心法來(lái)解決的。但是YY都是選擇了貪心，貪心，貪心！于是我們得出了結(jié)論YY只會(huì)使用貪心*_* 事實(shí)上，當(dāng)我們遇到了一些比較難的題目的時(shí)候，也許尋找最優(yōu)算法并非是最好的選擇，而貪心才是：王道【名人名言】 同樣高、同樣重、同樣聰明甚至擁有同樣性格同樣閱歷的人，未必會(huì)使用同一種貪心。 YY 的確，貪心是不是有用，還是要看怎么用。比如說(shuō)，我們來(lái)看看一些例子：穿越磁場(chǎng)（CROSS

3、）探險(xiǎn)機(jī)器人在Samuel星球上尋找一塊奇特的礦石，然而此時(shí)它陷入了一片神秘的磁場(chǎng)區(qū)域，動(dòng)彈不得。探險(xiǎn)空間站立刻掃描了這片區(qū)域，繪制出該區(qū)域的磁場(chǎng)分布平面圖。這片區(qū)域中分布了N個(gè)磁場(chǎng)，每個(gè)磁場(chǎng)呈正方形，且邊與坐標(biāo)軸平行。例如下圖中，存在3個(gè)磁場(chǎng)，白點(diǎn)表示機(jī)器人的位置，黑點(diǎn)表示礦石的位置：XYO科學(xué)家們分析平面圖，進(jìn)一步發(fā)現(xiàn)：這些磁場(chǎng)為大小不一的正方形，可能相交，甚至覆蓋，但是它們的邊緣不會(huì)重合，頂點(diǎn)也不會(huì)重合。例如下面的兩種情形是不會(huì)出現(xiàn)的：科學(xué)家們給探險(xiǎn)機(jī)器人啟動(dòng)了磁力罩，這樣它就可以在磁場(chǎng)中自由穿越了。初始時(shí)，探險(xiǎn)機(jī)器人和所有礦石都不在任何磁場(chǎng)的邊緣。由于技術(shù)限制，在穿越過(guò)程中機(jī)器人只能夠

4、水平或垂直移動(dòng)，且不能夠沿著磁場(chǎng)的邊緣行動(dòng)。由于磁力罩的能量有限，科學(xué)家們希望探險(xiǎn)機(jī)器人穿越盡量少的磁場(chǎng)邊緣采集到這塊礦石。例如上圖中，探險(xiǎn)機(jī)器人最少需要穿越兩次磁場(chǎng)邊緣。現(xiàn)在小聯(lián)請(qǐng)你編寫(xiě)程序，幫助科學(xué)家們?cè)O(shè)計(jì)探險(xiǎn)機(jī)器人的路線，統(tǒng)計(jì)探險(xiǎn)機(jī)器人最少需要穿越多少次磁場(chǎng)邊緣。但是如果用離散化來(lái)做，顯然比較麻煩。似乎有比較多的細(xì)節(jié)要處理那么能不能貪心呢？！ 這是一道很眼熟的題目！王凈晶說(shuō)這是離散化然后再寬搜，然后再若干若干不錯(cuò)！這是一道離散化的題！ 本題之所以能夠使用離散化，是因?yàn)樗⒅氐氖窍鄬?duì)位置，而不是絕對(duì)位置，這本質(zhì)上其實(shí)是一種簡(jiǎn)單的拓?fù)渥儞Q。而其實(shí)本題中的矩形就是滿足拓?fù)湫再|(zhì)的。 關(guān)于拓?fù)洌?/p>

5、我們很容易想到了一個(gè)和本題相關(guān)的比較著名的拓?fù)鋵W(xué)的定理： 封閉圖形的某一點(diǎn)與圖形外的某一點(diǎn)的連線必然至少與圖形的邊相交1次?！舅伎肌恳粫r(shí)間我希望大家能夠浮想聯(lián)翩1次這給了我們一個(gè)啟示： 如果只有一個(gè)正方形，并且一個(gè)點(diǎn)在正方形內(nèi)，一個(gè)在正方形外，那么顯然如果一個(gè)點(diǎn)要到達(dá)另一個(gè)點(diǎn)，必須要經(jīng)過(guò)這個(gè)正方形的至少一條邊。 擴(kuò)展地講，如果對(duì)于x個(gè)正方形而言，兩個(gè)點(diǎn)都是恰好一個(gè)在正方形內(nèi)部，一個(gè)在正方形外部，顯然一個(gè)點(diǎn)要到達(dá)另一個(gè)點(diǎn)，至少要經(jīng)過(guò)x條邊。 那么我們就可以求出答案的一個(gè)下限。即從一個(gè)點(diǎn)要到達(dá)另一個(gè)點(diǎn)，經(jīng)過(guò)這一種必然要經(jīng)過(guò)的正方形的邊，需要多少次。 這個(gè)時(shí)候我們也許會(huì)有些激動(dòng)，然后考慮這兩種情況：

6、 是不是如果遇到這兩種情況，就可以繞掉正方形呢？ 如果是這個(gè)樣子，那么問(wèn)題就解決了。 因?yàn)閮蓚€(gè)點(diǎn)與一個(gè)正方形的位置關(guān)系只可能是一內(nèi)一外，兩個(gè)都在正方形內(nèi)部或者兩個(gè)都在外部。后兩種情況都不需要經(jīng)過(guò)正方形的邊，那么我們需要輸出的結(jié)果就是一共有多少正方形滿足兩個(gè)點(diǎn)一個(gè)在它內(nèi)部一個(gè)在它外部。 還記得當(dāng)年貪心大師盧俊想到了這個(gè)方法，拍案而起，語(yǔ)驚四座。于是幾乎所有的人都震驚了！ 但是這一下子惹惱了那些離散化的流派。他們感覺(jué)心中如此不平衡（因?yàn)檫@個(gè)方法與他們的離散化相比未必太簡(jiǎn)單了），當(dāng)即眾志成城，幾乎是在瞬間就找到了一個(gè)反例：這樣的話，按照貪心的算法，就不需要經(jīng)過(guò)任何邊，但是事實(shí)上卻要經(jīng)過(guò)至少兩條邊。很

7、可惜，這種貪心是錯(cuò)誤的！但是，錯(cuò)誤的貪心就是沒(méi)用的貪心么？！不！ 測(cè)試數(shù)據(jù)中又能有多少這樣的反例呢？就算是這么個(gè)錯(cuò)誤的貪心，當(dāng)年的貪心大師盧俊也僅錯(cuò)了1個(gè)點(diǎn)！ 再退一步來(lái)說(shuō)，在這個(gè)貪心結(jié)論的基礎(chǔ)之上，也許我們只需要討論一些簡(jiǎn)單的反例，就可以比較簡(jiǎn)潔地解決這道題？大家可以思考思考這一題到此結(jié)束，下面我們來(lái)看下一題：矩陣（matrix） 給定一個(gè)矩陣（即矩陣中的元素僅為或），每次操作可以選擇某一行或某一列，將其中的全部刪除。 問(wèn)最少必須進(jìn)行多少次操作，才可以將矩陣中所有的全部刪除。 這題希望大家比較熟悉。這是前年的某一次淘汰賽的試題，應(yīng)該來(lái)說(shuō)是相當(dāng)簡(jiǎn)單的二分圖匹配，但是我遇到了很多當(dāng)時(shí)還不會(huì)二分圖

8、匹配的人，他們都是使用貪心來(lái)解決這道題的。應(yīng)該這么說(shuō)，貪心來(lái)做本題比二分圖匹配更加曲折而富有朝氣（雖然未必能夠拿滿分）。當(dāng)然，在眾多的貪心者中，仍是可以找到貪心大師盧俊的影子。1.因?yàn)槊恳粋€(gè)1都是要被刪除的，所以考慮每一個(gè)1所在行和所在列。哪個(gè)包含的1多就刪除哪個(gè)。直到刪光為止。2.考慮每一行（列），哪一個(gè)包含的1多就刪除哪個(gè)。一直到所有的1都刪光為止。3.考慮如果有某一行或者某一列只有一個(gè)1，那么必然刪除那個(gè)1所在的列或者行（因?yàn)榭偸且獎(jiǎng)h除這個(gè)1的，如果單單地刪除這一行或者列，那么顯然是不太合算的）。這樣刪直至不存在某一行或者某一列只有一個(gè)1。那么剩下的只要一行一行地刪就可以了。這里介紹幾種

9、我印象比較深的貪心方法： 第一種和第二種貪心的方法比較容易想到，但是第三種就可能需要一點(diǎn)功夫。而且看起來(lái)第三種貪心方法更有道理一點(diǎn)。事實(shí)上第三種貪心方法獲得了滿分的好成績(jī)（而別的方法都只有40分50分的樣子）。這讓我們想到了【名人名言】 越是有道理的貪心，效果就越好。 YY 的確如此！這個(gè)貪心的方法是我們學(xué)校的張紫東想到的方法，他花了一定的時(shí)間想到了這個(gè)算法，并且一度認(rèn)為它是非常好的數(shù)學(xué)方法因而比較高興。但是由于我的同學(xué)趙晟在幾乎是瞬間尋找到了一個(gè)反例，使這個(gè)解法的本質(zhì)變成了貪心。 但是由此我們看到，不同的貪心方法效果是有很大的差別的。至少選擇一種更有力的貪心方法，可以讓你事半功倍。 而對(duì)于貪

10、心的題目，貪心大師盧俊總是有著非凡的表現(xiàn)。他選擇的是綜合貪心的方法，雖然他沒(méi)有想到張紫東的貪心方法，但是仍然是只錯(cuò)了1個(gè)點(diǎn)，這是非常好的成績(jī)了。所謂的綜合貪心，就是把多種的貪心方法聯(lián)合在一起，統(tǒng)統(tǒng)實(shí)現(xiàn)一遍，然后選出一個(gè)最優(yōu)解。我們可以看到這種方法是相當(dāng)不錯(cuò)的方法。因?yàn)閷?duì)于只要輸出一個(gè)最優(yōu)解的問(wèn)題而言，如果能夠?qū)⒍鄠€(gè)貪心方法聯(lián)合在一起，就可以達(dá)到互補(bǔ)的效果，從而可以避免相當(dāng)一部分的反例。因此對(duì)于貪心的題目，最好能夠盡可能多地尋找各種各樣有可能正確的貪心方法，不斷地為自己增加獲勝籌碼?！久嗣浴?貪心，無(wú)論是方法還是結(jié)果，向來(lái)都是多多益善的。 YYMatrix 給定一個(gè)0-1矩陣，我們可對(duì)其各行

11、、各列中的“1”的個(gè)數(shù)進(jìn)行統(tǒng)計(jì)。例如對(duì)于一個(gè)34的矩陣： 其中各行包含“1”的個(gè)數(shù)分別是1,3,2;各列包含“1”的個(gè)數(shù)分別是2,1,2,1。 對(duì)于一個(gè)0-1矩陣，給定各行包含的“1”的個(gè)數(shù)r1,r2，rn，以及各列包含“1”的個(gè)數(shù)c1，c2，cm。同時(shí)，指定一些矩陣中的一些元素必須為0，題目保證每行，每列至多有一個(gè)必須為0的元素。你的任務(wù)是判斷是否存在滿足上述要求的01矩陣。但是如果用網(wǎng)絡(luò)流來(lái)做，顯然比較麻煩。似乎有比較多的細(xì)節(jié)要處理而且大家回憶數(shù)據(jù)規(guī)模還可能超時(shí)那么能不能貪心呢？！ 這是一道很眼熟的題目！王凈晶說(shuō)這是建圖然后再網(wǎng)絡(luò)流，然后再若干若干不錯(cuò)！這是一道網(wǎng)絡(luò)流的題！ 我曾經(jīng)試圖尋找

12、貪心大師盧俊的身影，但是很遺憾，在這一題上他似乎失去了往日的光輝。是的，本題他貪心了，但是只有45分這是令人遺憾的。這也說(shuō)明，貪心不光是需要經(jīng)驗(yàn)，還是需要能力和技巧的，甚至運(yùn)氣。像貪心大師盧俊這樣的人也會(huì)有小小的失誤，這告訴我們?cè)谫悎?chǎng)上，尤其是當(dāng)你使用貪心的時(shí)候，是從來(lái)不會(huì)有常勝將軍的。 只有不斷地提升自己的實(shí)力，挖掘自己的潛力，然后深刻分析和理解貪心的本質(zhì)，才可能會(huì)能夠完成一個(gè)又一個(gè)美滿的貪心。 于是我此時(shí)要介紹的是我的同學(xué)趙晟。他無(wú)疑是本題的最成功的貪心者，他獲得了滿分的好成績(jī)。也許網(wǎng)絡(luò)流也能獲得150分，我不知道在1000的規(guī)模下能不能不超時(shí)。但是趙晟同學(xué)用他的行動(dòng)證明了，貪心是如此有力

13、！ 下面講述一下他的方法。 首先他試圖尋找一種最優(yōu)的擺放1的方案，即如果不存在這樣的一種方案，那么就可以認(rèn)為是無(wú)解的。 那么怎么樣才是最優(yōu)的呢？ 他是一列一列地掃的。先不考慮那些必然是0的格子。如果掃到了當(dāng)前列，發(fā)現(xiàn)當(dāng)前列理應(yīng)有x個(gè)1。那么考慮所有的行。如果我們能夠找到x行，每一行當(dāng)前擁有的1的個(gè)數(shù)都是非零的，那么我們自然可以安排這x行，每一行的這一列都填上1。然后這x行當(dāng)前擁有的1的個(gè)數(shù)都要減去1。這是顯然的。 問(wèn)題是如何將擺放的方案最優(yōu)化?？梢栽O(shè)想，如果每一次掃一列的時(shí)候都可以找到足夠多的含1行（越多越好），那么顯然方案就是優(yōu)的。如果每一次掃一列都盡可能地不去使用含1比較少的那些行，使用含

14、1比較多的那些行，那么無(wú)形中似乎就是節(jié)約了行的個(gè)數(shù)這個(gè)資源，從而在以后更有選擇余地，不會(huì)出現(xiàn)諸如某一列明明有5個(gè)1，但是當(dāng)前只有4個(gè)含1的行了。 帶著這么一種騰出更多的選擇余地的思想，我們?nèi)菀琢私獾狡鋵?shí)我們只要在每一次選擇含1行的時(shí)候選擇含1最多的前x行就可以了，這樣就是保證最優(yōu)的。 但是無(wú)疑那些已經(jīng)確定為0的格子是相當(dāng)討厭的，這個(gè)條件讓貪心無(wú)所適從?？墒穷}目中的另一個(gè)條件給了我們這些貪心的選手不小的信心，即這種格子每行每列至多只會(huì)出現(xiàn)1次。 使用網(wǎng)絡(luò)流的同學(xué)可以發(fā)現(xiàn)，這個(gè)條件對(duì)于網(wǎng)絡(luò)流而言是多余的，是可以忽視的；但是這個(gè)條件對(duì)于貪心選手而言絕對(duì)是一個(gè)福音。 貪心新秀趙晟如是說(shuō)： 這是一個(gè)轉(zhuǎn)折

15、點(diǎn)。 的確如此。 趙晟認(rèn)為，這個(gè)條件給了他一個(gè)很好的第二關(guān)鍵字，即根據(jù)每一行的0的出現(xiàn)位置進(jìn)行排序。更清晰地說(shuō)，對(duì)于擁有同樣個(gè)數(shù)的1的行，我們優(yōu)先選擇的是已經(jīng)確定的0的位置更靠后的那個(gè)。他貪心地認(rèn)為這種選擇是最優(yōu)的選擇方案。 我猜想貪心新秀趙晟的選擇一定有他的道理。因?yàn)槲以噲D將他的第二關(guān)鍵字修改為完全相反的情況的時(shí)候，測(cè)試數(shù)據(jù)是如此地有力以至于那個(gè)程序僅對(duì)了一個(gè)點(diǎn)。 但是他在考場(chǎng)上到底是如何思考的，為什么他會(huì)選擇這么一個(gè)關(guān)鍵字，至今已經(jīng)無(wú)人能知。趙晟事后回憶： 我當(dāng)時(shí)覺(jué)得這樣可能好一點(diǎn)但是其實(shí)這個(gè)方法并不是很好，你知道，我當(dāng)時(shí)在幾乎是瞬間就發(fā)現(xiàn)了一個(gè)致命的反例！ 于是一時(shí)間大家都開(kāi)始尋找趙晟在

16、考場(chǎng)上瞬間就發(fā)現(xiàn)的反例。但是很遺憾的是在很長(zhǎng)的一段時(shí)間大家都沒(méi)有發(fā)現(xiàn)任何的反例。 無(wú)奈的人們?cè)?jīng)向趙晟求助。后來(lái)趙晟發(fā)來(lái)信息，說(shuō)： 可能是我當(dāng)時(shí)想錯(cuò)了。也許沒(méi)有反例。 于是我們又一度認(rèn)為這個(gè)是正確的方法。 而現(xiàn)在我通過(guò)努力，終于尋找到了一個(gè)反例。 但無(wú)論如何，這無(wú)疑是一個(gè)非常了不起的發(fā)現(xiàn)。因?yàn)檫@個(gè)被認(rèn)定了是網(wǎng)絡(luò)流強(qiáng)剪枝的題目，竟然可以用貪心來(lái)做！這對(duì)于喜愛(ài)貪心的選手顯然是振奮人心的消息。 這里順便介紹一下我的方法。在考場(chǎng)上我錯(cuò)誤地認(rèn)為必然是0的格子這個(gè)條件是沒(méi)有多少用處的，因而比較從容地忽略了它。 如果某一個(gè)格子必然是0，那么我把這個(gè)格子變成1。這個(gè)格子所在的行和列的1的個(gè)數(shù)加1。然后我就把原

17、問(wèn)題轉(zhuǎn)換成了一個(gè)不存在必然是0的格子的模型。然后在這個(gè)模型的基礎(chǔ)之上，就可以比較容易地貪心（可以證明這是正確的）。 不過(guò)我忽視了一個(gè)比較關(guān)鍵的地方。我的轉(zhuǎn)換只是必要的，而并不是充分的。比如在轉(zhuǎn)換后的模型下是有擺放方案的，但是在原模型下就未必是有擺放方案的。 事實(shí)上這樣的貪心是有比較好的效果的。當(dāng)然我們也可以說(shuō)是測(cè)試數(shù)據(jù)過(guò)弱了，但是誰(shuí)能否認(rèn)我的創(chuàng)新的能力和貪心的勇氣呢？【名人名言】 很多時(shí)候，你并不是缺少貪心的思想，而是缺少貪心的勇氣。 YY 退一步思考，將問(wèn)題轉(zhuǎn)換為別的模型，或者是自制一個(gè)“序”，也能夠收到意想不到的效果。 YY 以上介紹的是一些題目可以用貪心來(lái)獲得部分分，但是這部分分究竟有多

18、少?zèng)]有多少人知道，不僅要看貪心的方法是否得當(dāng)，還要看測(cè)試數(shù)據(jù)的好壞。這也是許多人選擇標(biāo)準(zhǔn)算法舍棄貪心的主要原因。 但是我們必須要明確的一點(diǎn)是，貪心并不是在每一個(gè)時(shí)刻都是不完備的，下面我們要講的就是完備的貪心算法。貪心有理【名人名言】 當(dāng)你因?yàn)槟骋坏李}你根本就找不到一個(gè)真實(shí)可靠的算法而惶恐的時(shí)候，也許你只是漏了貪心。 YY多個(gè)關(guān)鍵字的排序(keys)時(shí)限：6s內(nèi)存限制：10MB考慮一個(gè)有C列的表格。為了簡(jiǎn)單起見(jiàn)，表格中的元素均為小寫(xiě)字母組成的字符串。Col. 1Col. 2Col. 3Col. 1Col. 2Col. 3Col. 1Col. 2Col. 3appleredsweetbananab

19、rownrottenapplegreensourapplegreensourapplegreensourappleredsweetpeargreensweetpeargreensweetbananabrownrottenbananayellowsweetappleredsweetbananayellowsweetbananabrownrottenbananayellowsweetpeargreensweet表格1 表格 2 表格3 給出了sort（k）這么一個(gè)過(guò)程，它將會(huì)根據(jù)第k列的元素的大小進(jìn)行排序，以一行為單位。這個(gè)排序是穩(wěn)定的，即如果有兩行在k列的元素大小相等，那么它們將會(huì)保持相對(duì)的位置

20、不變。對(duì)于表格1使用sort（2）過(guò)程，就得到了表格2。 我們對(duì)于這種操作的序列很感興趣。這些操作將統(tǒng)統(tǒng)作用于一個(gè)表格，并且是嚴(yán)格地根據(jù)操作的序列順序進(jìn)行的。例如對(duì)于表格1，先sort（2），再sort（1），就得到了表格3。 如果對(duì)于任意的表格，兩個(gè)操作序列都會(huì)有相同的效果，那么這兩個(gè)操作序列就被認(rèn)為是相同的。比如說(shuō)，sort（2）；sort（2）；sort（1）和sort（2）；sort（1）是相同的。但是它們和sort（1）；sort（2）是不同的，因?yàn)樗鼈冏饔糜诒砀?的時(shí)候，會(huì)有不同的效果。 你的任務(wù)是，給你一串操作序列，請(qǐng)你找到最短的與它相同的序列，輸出它的長(zhǎng)度。（1 C 1 000

21、 000，1 N 3 000 000） 這是CEOI2005的一道題，我和姜嘯曾經(jīng)認(rèn)真地討論過(guò)此題應(yīng)該如何解決。也許動(dòng)態(tài)規(guī)劃，也許并查集，也許網(wǎng)絡(luò)流，但是當(dāng)我們仔細(xì)地看到它的數(shù)據(jù)規(guī)模的時(shí)候，我們才清晰地認(rèn)識(shí)到此題必然是貪心，至少有一種比較簡(jiǎn)易的方法。 于是考慮如何貪心。我們研究出來(lái)了一個(gè)比較有意思的小定理： 如果某一個(gè)操作序列含有局部的重復(fù)的話（諸如sort(a);sort(b); sort(a);sort(b)），那么可以將重復(fù)部分刪去，因?yàn)檫@些部分是沒(méi)用的。 這是姜嘯用數(shù)學(xué)歸納法證明的一個(gè)結(jié)論。這的確是一個(gè)不錯(cuò)的啟發(fā)。但是怎么運(yùn)用這個(gè)解決本題呢？ 序列長(zhǎng)最大為3000000，時(shí)限為6s，這

22、就逼迫我們使用諸如O（n）或者O（n log n）的算法。那么怎么在O（n log n）的時(shí)間內(nèi)判重呢？ 歡迎大家思考一下。 我們思考了相當(dāng)部分的時(shí)間，可是還是沒(méi)有想到應(yīng)該怎么實(shí)現(xiàn)。于是我一度懷疑姜嘯的證明錯(cuò)了。我又自己重新證明了一遍。 但是通過(guò)自己證明，我得到了一個(gè)更強(qiáng)的結(jié)論： 從后向前掃描，若某一個(gè)操作出現(xiàn)了多次，那么除了第一個(gè)發(fā)現(xiàn)的操作有意義，其余都是沒(méi)有意義而可以忽略的。 具體的我的想法如下： 首先，可以把一系列的操作看作是一種多重的排序，起關(guān)鍵作用的顯然是最后一次的排序了。那么前面的排序會(huì)不會(huì)產(chǎn)生一定的影響呢？看到題目中說(shuō)這是一種穩(wěn)定的排序，所以我們知道： 當(dāng)且僅當(dāng)最后一次排序之后，

23、兩個(gè)數(shù)是相同的，那么它們的相對(duì)位置才不是最后決定的（我們不妨稱這種情況為不能確定），否則它們的相對(duì)位置均由最后的一次操作決定。 那么如果兩數(shù)相同，它們的相對(duì)位置是由什么決定的呢？ 因?yàn)檫@是穩(wěn)定的排序，所以我們想到它們的相對(duì)位置必然是由之前的操作決定的。 如果在倒數(shù)第二次操作的時(shí)候，它們所在行的相對(duì)位置不是不能確定，那么它們的相對(duì)位置就將保持到最后；如果它們所在行的相對(duì)位置還是不能確定，那么我們可以繼續(xù)看倒數(shù)第三次操作。 這樣我們就很清晰地聯(lián)想到了按第一第二第n關(guān)鍵字排序。事實(shí)上，這么一個(gè)操作序列的本質(zhì)就是按照第一第二第n關(guān)鍵字排序。 進(jìn)一步想，因?yàn)槿绻骋淮闻判颍骋粋€(gè)關(guān)鍵字既是第一關(guān)鍵字，又

24、是第x關(guān)鍵字，那么后一個(gè)關(guān)鍵字顯然是沒(méi)有意義的，因?yàn)楫?dāng)且僅當(dāng)?shù)谝魂P(guān)鍵字相同的時(shí)候才會(huì)考慮后面的關(guān)鍵字。所以某一個(gè)操作序列能夠被縮短當(dāng)且僅當(dāng)該操作序列有相同的操作。而且，如果要縮短操作序列，只需要去掉所有多余的重復(fù)操作，保留最后一個(gè)就行了。 至此本題的算法就變得簡(jiǎn)單易行了。這的確是非常簡(jiǎn)單的貪心，但是通過(guò)這個(gè)例題我們發(fā)現(xiàn)，貪心也是很需要技巧的。要知道如何貪心，不僅要牢牢地抓住問(wèn)題的本質(zhì)，而且還要學(xué)會(huì)理性地分析，從各個(gè)角度觀察和思考，找到最切合實(shí)際的方法。 雖然這只是一道比較簡(jiǎn)單的問(wèn)題，但是一旦陷入思維定式（比如剛開(kāi)始就想錯(cuò)了方向），就會(huì)感到無(wú)從下手。我認(rèn)為想要好好貪心，不僅要敢于下手，還要敢于放

25、手，學(xué)會(huì)換角度思考。當(dāng)然做別的事情也是如此，只是我認(rèn)為在貪心方面尤為重要罷了?！久嗣浴?只有一個(gè)學(xué)識(shí)淵博、胸襟寬闊、才思敏捷、敢于創(chuàng)新、善于突破、能屈能伸的人，才可能真真正正地學(xué)好貪心。 YY售票處 一個(gè)售票處賣演唱會(huì)的門票。但是它總是賣長(zhǎng)度固定的連續(xù)座位的票而不再是單張票單張票地賣。售票處收到了一堆的訂單。一個(gè)訂單僅用在需要訂的連續(xù)座位中的編號(hào)最小的座位號(hào)（即一個(gè)數(shù)字）表示。 售票處可能不能滿足所有的訂單的需求。并且，如果只是按照訂單上安排的那樣去賣票，那么可能會(huì)有大批的座位是空著的。因此，售票處有以下的安排和定價(jià)策略。如果一個(gè)訂單被采納并且分配給買方的座位恰為訂單所要求的連續(xù)座位，那么

26、買方將付2元（這種票不妨被稱為原定票）。如果一個(gè)訂單被采納但是分配給買方的連續(xù)座位并非是訂單所要求的連續(xù)座位（只要有一個(gè)座位不同就視作不同），那么買方將付1元（這種票稱為改訂票）。如果一個(gè)訂單沒(méi)有被采納，那么顯然就沒(méi)錢可賺。：） 作為一個(gè)商人，你顯然想賺最多的錢。那么請(qǐng)輸出最多能賺多少錢，并輸出任意方案。 此題也是很有意思的一道題，怎么做呢？初看不是很清楚，但是如果用動(dòng)態(tài)規(guī)劃來(lái)做狀態(tài)量可能比較大，沒(méi)法來(lái)做，所以就想到了貪心。 首先想到應(yīng)該都是按照顧客的意思辦比較賺（畢竟顧客就是上帝么），是不是放越多的原定票越好呢？ 因?yàn)槟硞€(gè)地方要放一個(gè)原定票，但是卻有兩個(gè)改訂票和這塊區(qū)域有交集（至多只有兩個(gè)改

27、訂票），那么我如果放原定票是更加合算一點(diǎn)點(diǎn)（因?yàn)椴粌H得到的錢一樣多，而且占的空間小了）。 所以我們就知道了，放盡可能多的原定票是最優(yōu)的。我們已經(jīng)向成功邁了關(guān)鍵的一步：） 此時(shí)的CMC在這個(gè)基礎(chǔ)之上有了一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃。用optI表示在前i個(gè)格子里最多能夠有多少改訂票。然后再動(dòng)態(tài)規(guī)劃就比較容易了（因?yàn)槲覀冏C明了一定要盡可能多地放原定票，那么其實(shí)前i個(gè)格子里要買多少?gòu)堅(jiān)ㄆ笔且呀?jīng)決定了的）。顯然這種線性的動(dòng)態(tài)規(guī)劃是不會(huì)超時(shí)的，因此我認(rèn)為這是一個(gè)相當(dāng)好的基于已經(jīng)證明了的貪心的動(dòng)態(tài)規(guī)劃。一來(lái)程序不長(zhǎng)易于實(shí)現(xiàn)，二來(lái)整個(gè)方法也是比較容易想到的。 但是作為CEOI的一道題，官方給出的標(biāo)準(zhǔn)解答比較特殊，也許

28、這里很多的人都有所了解吧。下面還是也介紹一下。（主要參考了CEOI的官方解答） 第一步，試圖分配盡可能多的原定票。貪心地按照座位號(hào)遞減的次序來(lái)處理這些訂單。只要可行就為其分配座位。這是顯然正確的。 第二步，調(diào)整。如果pq，則顯然q滿足對(duì)于L的模比r小，那么顯然q浪費(fèi)的空間比r小，能放的改訂票不會(huì)少。 1.2 如果rq，則考慮最優(yōu)狀態(tài)的自r以后第一個(gè)出現(xiàn)的改訂票的位置p。自r到p，考慮這個(gè)范圍。首先兩種狀態(tài)含有的原定票是一樣多的，然后貪心狀態(tài)擁有的剛開(kāi)始的改訂票一張，最優(yōu)狀態(tài)擁有位置p的改訂票一張。因此貪心狀態(tài)不比最優(yōu)狀態(tài)劣。 1.3 如果rq，那么顯然兩種狀態(tài)意義是一樣的。 兩種狀態(tài)在前面的一

29、塊區(qū)域是等價(jià)的，那么可以同時(shí)刪去這一塊區(qū)域。這樣利用數(shù)學(xué)歸納的方法，不難證明這兩種狀態(tài)最后得到的總價(jià)值是相等的。 所以這種貪心方法是正確的。 但是我本人比較欣賞CMC的做法。因?yàn)橄褚陨系倪@種貪心手法是需要相當(dāng)?shù)募记傻模还馐秦澬募记桑易C明正確的時(shí)候還需要數(shù)學(xué)的證明技巧。我覺(jué)得如果貪心到某一步已經(jīng)可以用一種比較優(yōu)秀的方法完成這道題，那么就沒(méi)有必要繼續(xù)研究更精彩的做法，哪怕時(shí)間復(fù)雜度更低，更容易編寫(xiě)因?yàn)槲覀儾皇窃谏钊氲匮芯克惴?，我們要面?duì)的是信息學(xué)競(jìng)賽。 鄧小平爺爺說(shuō)過(guò)，能抓老鼠的貓就是好貓。因此我們要善于將貪心用于點(diǎn)點(diǎn)滴滴，幫助我們更好地解題，而不是追求一個(gè)虛無(wú)飄渺的“完美”貪心的過(guò)程?！久?/p>

30、人名言】 當(dāng)你已經(jīng)可以把蛇身畫(huà)出來(lái)的時(shí)候，就不用再去想要不要添只腳了。 YYMqueue 每個(gè)早晨，約翰的n頭（1=nmax(Ya+Xa+Xb, YaYbXb)可轉(zhuǎn)換為：min(Xa,Yb)min(Xb,Ya) 這也是不難理解的。因?yàn)閮深^奶牛一起擠奶的話，用時(shí)其實(shí)是Xa+Xb+Ya+Yb-公共用時(shí)。而公共用時(shí)min(Xa,Yb)（即Y先擠奶）或者min(Xb,Ya)（X先擠奶） 那么兩者中選大即可。 我們就此掌握了判斷交換奶牛順序是否更優(yōu)的方法。因此剩下的問(wèn)題變得很簡(jiǎn)單了。我們可以將這種方法變成關(guān)鍵字進(jìn)行排序，最后所得的序列即為最終序列?！久嗣浴?不斷地調(diào)整結(jié)果，通過(guò)貪心地獲得局部的較優(yōu)解不斷逼近最優(yōu)解，也是非常重要的貪心手段。 YYCow Acrobats Farmer John養(yǎng)了N(1=N=50,000)頭牛，她們已經(jīng)按1N依次編上了號(hào)。FJ所不知道的是，他的所有牛都?jí)粝胫鴱霓r(nóng)場(chǎng)逃走，去參加馬戲團(tuán)的演出?？赡膛兒芸彀l(fā)現(xiàn)她們那笨拙的蹄子根本無(wú)法在鋼絲或晃動(dòng)的的秋千上站穩(wěn)（她們還嘗試過(guò)把自己裝在大炮里發(fā)射出去，但可想而知，結(jié)果是悲慘的）。 最終，她們決定練習(xí)一種最簡(jiǎn)單的雜技：把所有牛都摞在一起，比如說(shuō)，第一頭牛站在第二頭