贪婪法并查集

1、貪婪法（ Greedy）Greedy 基本上就是一種簡化型的 DP，當你可以確定當前狀況就是接下來最好的狀況時，就可以直接使用了。也就是直接認為目前最好的，到了下一步還是會是最好的解，這無疑是一種很符合人性貪婪一面的算法。用介紹的實在很難說清楚，就讓我們直接來看例題吧！例題 1 工作排程 1給你 n 個事件，每一個事件都有它的開始時間和結束時間，而在一個時間內最多只能夠有一個事件，請問最多總共可以進行幾個事件？例題 2 工作排程 2給你 n 個工作，每個工作都有其截止期限 ti，而如果你在時限前沒做那個工作的話 ，則要付罰金 ci。如果做一個工作需要 1 單位的時間，則你最少要付多少罰金？例題

2、 3 誰先晚餐 ( TIOJ 1072 )給你 n 個要吃晚餐的人和一個廚師。當然那些人可以同時一起吃，但廚師一次只能做一道菜。給定每個人要吃的菜需要做多久 ，以及那個人需要吃多久 ，試問至少要多少時間 ，才能讓全部人都吃完？例題 4Setting Problems ( ACM 11269 )給你 n 個工作，每個工作都分為前段跟後段，各需要ai 和 bi 的時間。現在有兩台機器，一台負責處理前段工作，一台負責處理後段工作。而一個工作前段處理完後才能處理後段。請問至少要多少時間才能處理完所有工作？例題 5Shoemakers Problem ( ACM 10026 )給你 n 個工作，你每項工

3、作需要花 ti 天才能完成，而從你開始工作算起，每過一天，如果第i 個工作沒有完成的話，你就要付出 ci 的罰金，請問你要以何種順序進行這n 項工作，才能使付出的罰金最少呢？例題 6背包問題給你 n 個物品，每個物品都有其數量和價值，現在你有一個可以裝w 個東西的背包，請問你最多可以裝到多少價值的東西？例題 7Minimal Coverage ( ACM 10020 )給你 n 段線段 a , b ，請問你至少需要幾段線段，才能覆蓋住 0, M 這段線段？ii例題 8LIS but not LIS ( TIOJ 1240 )給你一個有 n 個正整數的序列，請你把它分拆成最少條的序列，使得每個序

4、列都是嚴格遞增的。例題 9經濟編碼 ( TIOJ 1155 )給你一個要壓縮的純文字檔案 ，壓縮方法是把每一個字元轉換成一個由0 和 1 組成的序列 。但是為了可以分辨所有的字元， 你要確定沒有一個序列會是另外一個序列的前綴。現在給你每個字元出現的次數，請問你要如何編碼才能使最後編出來的字串最短？Example: 原先的編碼方式：字元 /出現次數a/5b/3c/4d/9e/6原本二進位碼11000011100010110001111001001100101原本檔案長度是7*5 + 7*3 + 7*4 + 7*9 + 7*6 = 189 bits 。其中一種最佳的對應方法：新的二進位碼10000

5、0010111這麼編碼的檔案長度是2*5 + 3*3 + 3*4 + 2*9 + 2*6 = 61 bits 。例題 10 Packets ( ACM 311 )給你一些 1*1 、2*2 、3*3 、 4*4、 5*5 、6*6 的貨物，而你要把他們裝進一些6*6少需要多少個貨櫃？例題 11 Camel trading ( ACM 10700 )的貨櫃中，請問最給你一個由正整數、加號和乘號組成的算式，請問在加上括弧後，這個運算式的最大值和最小值是多少？例題 12 Product of digits ( ACM 993 )給你一個正整數n，請你找出一個最小的正整數Q，使得 Q 的每個位數乘積是

6、例題 13 零錢問題給你無限量個一元、五元、十元、二十元、五十元、一百元的硬幣，現在你要湊出少需要多少個硬幣？例題 14 Shopaholic ( ACM 11369 )n。n 元來，請問最給你 n 樣物品的價錢，你現在每買三樣以上的物品，最便宜的那個物品就不用錢。請問在買完全部物品後，你最多共可以省下多少錢？ (和所有物品的總價錢相比 )例題 15 寵物雞問題( TIOJ 1231 )給你一個電子寵物雞遊戲，遊戲中有若干種食物，每種食物都有固定的熱量、保存期限。每分鐘你可以從這些食物中選擇一種餵食寵物雞，但不可餵食過期的食物。而餵食每單位熱量會使體重增加1 公斤，而如果這分鐘沒有餵食，體重會

7、減少1 公斤。給定的食物種類、熱量、保存期限，以及終止時間，找出最大的體重增加量。例題 16 The Grand Dinner ( ACM 10249 )給你 m 個團體和 n 張桌子，第 i 個團體有 ai 個人，第 j 桌子最多只能坐 bj 個人。現在每個團體的人都不想和自己同一個團體的人坐同一張桌子 ，請問有沒有滿足上列條件的安排方式， 如果有請輸出其中一種安排方式。例題 17 刪位數的問題( TIOJ 1397 )給你一個 n 位數的正整數 A，請問刪除其中 k 位數 ( k y.rank2 then y.parent x3 elsex.parent y4if x.rank = y.r

8、ank5then y.rank y.rank +1?查找Find-Set(x)查找 x 屬於哪個集合，回傳x 所屬集合的代表。FIND -SET (x)1 if x.parent x2 then x.parent FIND -SET (x.parent)3 return x.parentUnion Find 的均攤分析時間複雜度為O(m(n)，其中 m 為總共進行了幾次Union-Find 操作， n 為元素總數， (n)為 Ackermann 函數的反函數，其值在n時 5，所以幾乎可視為常數。例題 Friends ( ACM 10608 )給你一個有 N 個居民的小鎮。當然其中有許多人是朋友的關係。根據有名的諺語： 我朋友