NOIP中的貪心

1、NOIP中的貪心Greedy Algorithm貪一貪就有分了哈哈哈定義 將整個問題分成若干個子問題 通過每個子問題的最優(yōu)解求出整個問題的最優(yōu)解是不是so easy 就像在n*m的矩陣中，每行取一個數(shù)，使它們的和最大 不用說你也知道怎么做 但是. 你覺得考試有那么裸么？ 開玩笑！注意 當(dāng)且僅當(dāng)每個當(dāng)前最優(yōu)解的選擇能導(dǎo)出總體最優(yōu)解，才能用貪心 當(dāng)然，你必須選對拿什么貪，或者說，什么策略 搞得像犯罪一樣.能貪么？ 比如0-1背包，肯定不能按單位體積價值去貪心 但是部分背包可以 我相信你能分清它們 如果你分不清，RMB會告訴你NOIP2002均分紙牌均分紙牌問題描述有 N 堆紙牌，編號分別為 1，2

2、，, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)。可以在任一堆上取若于張紙牌，然后移動。移牌規(guī)則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4，4 堆紙牌數(shù)分別為：98176移動3次可達(dá)到目的：從 取 4 張牌放到 （9 8 13 10） - 從 取 3 張牌放到 （9 11 10 10）- 從 取 1 張牌放到（10 10 10 10）。輸 入：鍵盤輸入文件名。文件格式：N（N 堆紙牌，1

3、 = N = 100）A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）輸 出：輸出所有堆均達(dá)到相等時的最少移動次數(shù)。 是不是想大吼一句：“這是貪心？” 沒錯這就是，好好想想吧 接下來我要第一次試用ppt的SmartArt功能 你們先想著1.試題幾乎不可能是裸的所以要改一改2.只要把每堆的數(shù)減去平均數(shù)，各堆的正負(fù)就會不同把所有堆都變成0的次數(shù)，就是答案3.然后從左往右遍歷，把每堆的數(shù)移到后一堆即可注意如果出現(xiàn)0，要跳過不管，否則會多算NOIP1999攔截導(dǎo)彈某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意

4、的高度，但是以后每一發(fā)炮彈都不能 高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例：INPUT 389 207 155 300 299 170 158 65 OUTPUT 6（最多能攔截的導(dǎo)彈數(shù)）2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)） 話說這是我們的第一道貪心題 當(dāng)時直接理解錯題意 然后呵呵 所以如果理解對的話，很容易能想到貪心 對于每套系統(tǒng)，只需存它攔截的最

5、后一枚導(dǎo)彈的高度 如果新的導(dǎo)彈比所有系統(tǒng)能攔截的高度都高，那就再來一套 否則選擇能攔截該導(dǎo)彈的高度最低的系統(tǒng) 代碼很容易，不再cv 當(dāng)然，此題也可以動規(guī)解決，那就不是我的事情了NOIP2004 合并果子 【問題描述】在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多 多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗 的體力等于每次合并所耗體力之和。因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每

6、個果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?1、2堆合并，新堆數(shù)目為3，耗費體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費體力為 12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。 【輸入文件】輸入文件fruit.in包括兩行，第一行是一個整數(shù)n（1 = n = 10000），表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai（1 = ai = 20000）是第i種果子的數(shù)目?！据敵鑫募?/p>

7、輸出文件fruit.out包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于231。【樣例輸入】31 2 9【樣例輸出】15【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，保證有n = 1000；對于50%的數(shù)據(jù)，保證有n = 5000；對于全部的數(shù)據(jù)，保證有n =0, z = 0。 3、什么都不做。 注意，在一輪中每個元素只能選擇一種操作。 Alice 已經(jīng)玩了很久了， 但她并不知道自己已經(jīng)玩了多少輪。 現(xiàn)在給出最終的集合，請你輸出 Alice 最少玩的輪數(shù)。 【輸入格式】 從文件 multiset.in 中讀入數(shù)據(jù)。第一行為一個整數(shù)，描述最終集合的大小。第二行為個非負(fù)整數(shù)，為最終

8、集合的每一個元素。 【輸出格式】 輸出到文件 multiset.out 中。 輸出唯一一行，Alice 最少玩的輪數(shù)。 【樣例輸入】 Sample Input 1 1 0 Sample Input 2 4 1 1 1 1 Sample Input 3 5 0 3 0 3 0 對于每個數(shù)，有0或非0兩種情況 對于0，每次操作中將0成對合并 對于非0數(shù)，每次操作同時減一 于是對于所有的數(shù)，按數(shù)值統(tǒng)計出現(xiàn)次數(shù) n減到0需要n次，減去之前的總次數(shù)，再算剩余多少0 直到最大的數(shù)，再計算剩余的0 計算剩余所有0合并需要的次數(shù) 加上之前的次數(shù)，即為答案可是可是，怎么確定怎么貪心呢 很大程度上，你不知道，然后

9、就是拼人品 當(dāng)然，還是可以找找路子的比如一些模板 堆問題 最短路中的dijkstra和最小生成樹prim 活動安排之類比如 可以改變一些條件，轉(zhuǎn)化成一些不知道怎么形容的樣子 自己悟吧 可以試一試，舉反例，當(dāng)然這要靠人品，所以請積德行善 比如可以仔細(xì)觀察條件，然后找到單個數(shù)據(jù)的變化過程 。 真的很玄乎 貪心法的求解過程貪心法的求解過程 用貪心法求解問題應(yīng)該考慮如下幾個方面： （1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。 （2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構(gòu)成一個滿足問題的完整解。 （3）解決函數(shù)soluti

10、on：檢查解集合S是否構(gòu)成問題的完整解。 （4）選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目標(biāo)函數(shù)有關(guān)。 （5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應(yīng)付款。 貪心法的一般流程貪心法的一般流程 Greedy(C) /C是問題的輸入集合即候選集合 S= ; /初始解集合為空集 while (not solution(S) /集合S沒有構(gòu)成問題的一個解 x=select(C); /在候選集合C中做貪心選擇 i

11、f feasible(S, x) /判斷集合S中加入x后的解是否可行 S=S+x; C=C-x; return S; 貪心法的基本要素 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 子問題：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個決策D1，D2，Dn，對于任何一個整數(shù)k，1kn，以Dk作為問題的初始狀態(tài)，來進行以后的決策，這樣的問題就成為是原問題的一個子問題。 1.貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以

12、通過一系列局部最優(yōu)的選擇，換句話說，當(dāng)考慮做何種選擇的時候，我們只考慮對當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。這是貪心算法可行的第一個基本要素。 貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。 2.最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。這樣的問題 已知一些量將它們改變?yōu)橐环N固定的樣子 求最大最小值 最優(yōu)化問題 能分成多個子問題的問題 .很可能是貪心算法 應(yīng)該可以發(fā)現(xiàn)這些題貌似都能動規(guī)解決 當(dāng)然它們