刷題時，遇見過哪些巧妙的貪心演算法的題目？

1樓：lndjy

「EZEC-6」造樹 - 洛谷

比較巧妙的貪心，把看起來很難搞的樹限制和度數限制變成乙個容易處理的合併策略，然後可以暴力/資料結構優化/單調性優化，對應30/80/100分的做法。比較有趣和巧妙吧，被 rqy 表揚過（（（

我是出題人，但是這個做法是乙個神仙花了很長時間想出來的。

2樓：疏簾淡月

lc 968 Binary Tree Camera

solution裡面的greedy, 自己做的時候很難證明這個解法是正確的

3樓：劉宇波

果斷是Kruskal最小生成樹演算法。

Kruskal表述極其簡單，初學者一聽就能明白是如何執行的（怎麼實現是另外一回事）：將圖中所有邊排序，從最小的邊開始，看當前的邊和已經選為最小生成樹的邊是否構成環，如果沒有構成環就放入最小生成樹中，否則扔掉。最終就形成了圖的最小生成樹。

但是，這個演算法為什麼正確？卻很難一下子想明白。這其實這本身就是貪心演算法的特點。

一旦要使用貪心演算法，事情就變得簡單了。但真正困難的是：為什麼貪心是正確的。

這裡就不具體闡述Kruskal演算法背後的證明了，一搜一大堆。

不過我個人認為，如果抹去對最小生成樹問題經典解法的印象，把最小生成樹問題看做乙個全新的問題從零開始推倒的話，Kruskal的解法是更容易被推導出來。個人認為比Prim演算法自然。其實，Prim演算法也有貪心的意味，但是不夠直觀，如果是從0開始思考的，思維上也更繞一些。

另：哈夫曼樹也是乙個很巧妙的貪心演算法。

最後，我想借這個問題表達：很多精妙的演算法思想，其實就在經典的演算法中。經典的演算法之所以經典，就是因為其中蘊含著通用的演算法思維模型在裡面。

可惜很多演算法學習者，尤其是初學者，容易忽略經典，或許是因為覺得經典的東西就是平凡的吧。刻意去追求偏題怪題，最終的結果其實是沒有良好的演算法思維根基。

4樓：Birdman

瀉藥，退役OI選手強答一波。

貪心演算法為標算的題目現在比賽遇到的不多了。個人認為Noip2015的D2T3鬥地主的貪心策略還是比較巧妙的。

貪心演算法主要用在騙分上面，小資料暴力，大資料貪心有時會有奇效（曼哈頓距離）。

5樓：DQS

瀉藥。說到貪心，我腦中浮現出來兩個題。乙個是NOIP的國王遊戲，乙個是堆優化的經典問題，忘了出處了。

先說後者吧。題意是有n個任務，每天只能完成乙個任務，每個任務有deadline和價值。問如何安排使得受益最大。

我們發現乙個任務在deadline時做總不會差。但是有多個任務同時擠一天就需要取捨了，這時要選價值最大的那個。

於是策略是先按deadline排序，若能做則做，若這個任務有衝突需要取捨，那麼就捨棄當前已做任務序列中價值最小且比當前任務價值還要小的那個。

之所以感覺巧妙，是因為……符合實際（逃

啊其實並不是。我感覺這個實際上是一種降維。把兩個關鍵字的問題轉換成乙個關鍵字。

我第一次體會到這個思路就是做這個題。後來發現這個思路可以用在眾多資料結構或是計算幾何的題目中應用，並且非常好使。

對於前者，題意是給n個二元組，對於第i個元素，他的權值為，讓你排序後使得最大權值最小，求此時最大權值。

對那個權值排序。考慮相鄰兩個元素，考慮交換是否會變優。因為前面的元素不變，所以實際上是比較和，也就是對乙個二元組的x*y進行排序。

巧妙的原因……是因為這是第一次發現，考慮排序問題（推廣一下可以認為是對於集合中考慮元素交換問題），可以首先考慮相鄰元素交換，這樣問題會變的更簡單易懂。

據說這個題當年因為思路清奇被認為是神題，但是後來出爛大街了…

其實現在寫下這些，已經不覺得這些題有多巧妙了。現在想來，收穫最大的大概是從中汲取到的解題經驗，還有體會到的演算法之美。大概這也能算巧妙吧？