贪婪法并查集.docVIP

貪婪法（Greedy） Greedy基本上就是一種簡化型的DP，當你可以確定當前狀況就是接下來最好的狀況時，就可以直接使用了。也就是直接認為目前最好的，到了下一步還是會是最好的解，這無疑是一種很符合人性貪婪一面的算法。 用介紹的實在很難說清楚，就讓我們直接來看例題吧！ 工作排程1 給你n個事件，每一個事件都有它的開始時間和結束時間，而在一個時間內最多只能夠有一個事件，請問最多總共可以進行幾個事件？ 工作排程2 給你n個工作，每個工作都有其截止期限ti，而如果你在時限前沒做那個工作的話，則要付罰金ci。如果做一個工作需要1單位的時間，則你最少要付多少罰金？ 誰先晚餐 ( TIOJ 1072 ) 給你n個要吃晚餐的人和一個廚師。當然那些人可以同時一起吃，但廚師一次只能做一道菜。給定每個人要吃的菜需要做多久，以及那個人需要吃多久，試問至少要多少時間，才能讓全部人都吃完？ Setting Problems ( ACM 11269 ) 給你n個工作，每個工作都分為前段跟後段，各需要ai和bi的時間。現在有兩台機器，一台負責處理前段工作，一台負責處理後段工作。而一個工作前段處理完後才能處理後段。請問至少要多少時間才能處理完所有工作？ Shoemakers Problem ( ACM 10026 ) 給你n個工作，你每項工作需要花ti天才能完成，而從你開始工作算起，每過一天，如果第i個工作沒有完成的話，你就要付出ci的罰金，請問你要以何種順序進行這n項工作，才能使付出的罰金最少呢？ 背包問題 給你n個物品，每個物品都有其數量和價值，現在你有一個可以裝w個東西的背包，請問你最多可以裝到多少價值的東西？ Minimal Coverage ( ACM 10020 ) 給你n段線段[ai, bi]，請問你至少需要幾段線段，才能覆蓋住[0, M]這段線段？ LIS but not LIS ( TIOJ 1240 ) 給你一個有n個正整數的序列，請你把它分拆成最少條的序列，使得每個序列都是嚴格遞增的。 經濟編碼 ( TIOJ 1155 ) 給你一個要壓縮的純文字檔案，壓縮方法是把每一個字元轉換成一個由0和1組成的序列。但是為了可以分辨所有的字元，你要確定沒有一個序列會是另外一個序列的前綴。現在給你每個字元出現的次數，請問你要如何編碼才能使最後編出來的字串最短？ Example: 原先的編碼方式： 字元/出現次數 ‘a’/5 ‘b’/3 ‘c’/4 ‘d’/9 ‘e’/6 原本二進位碼 1100001 1100010 1100011 1100100 1100101 原本檔案長度是7*5 + 7*3 + 7*4 + 7*9 + 7*6 = 189 bits。 其中一種最佳的對應方法： 新的二進位碼 10 000 001 01 11 這麼編碼的檔案長度是2*5 + 3*3 + 3*4 + 2*9 + 2*6 = 61 bits。 Packets ( ACM 311 ) 給你一些1*1、2*2、3*3、4*4、5*5、6*6的貨物，而你要把他們裝進一些6*6的貨櫃中，請問最少需要多少個貨櫃？ Camel trading ( ACM 10700 ) 給你一個由正整數、加號和乘號組成的算式，請問在加上括弧後，這個運算式的最大值和最小值是多少？ Product of digits ( ACM 993 ) 給你一個正整數n，請你找出一個最小的正整數Q，使得Q的每個位數乘積是n。 零錢問題 給你無限量個一元、五元、十元、二十元、五十元、一百元的硬幣，現在你要湊出n元來，請問最少需要多少個硬幣？ Shopaholic ( ACM 11369 ) 給你n樣物品的價錢，你現在每買三樣以上的物品，最便宜的那個物品就不用錢。請問在買完全部物品後，你最多共可以省下多少錢？(和所有物品的總價錢相比) 寵物雞問題 ( TIOJ 1231 ) 給你一個電子寵物雞遊戲，遊戲中有若干種食物，每種食物都有固定的熱量、保存期限。每分鐘你可以從這些食物中選擇一種餵食寵物雞，但不可餵食過期的食物。而餵食每單位熱量會使體重增加1公斤，而如果這分鐘沒有餵食，體重會減少1公斤。給定的食物種類、熱量、保存期限，以及終止時間，找出最大的體重增加量。 The Grand Dinner ( ACM 10249 ) 給你m個團體和n張桌子，第i個團體有ai個人，第j桌子最多只能坐bj個人。現在每個團體的人都不想和自己同一個團體的人坐同一張桌子，請問有沒有滿足上列條件的安排方式，如果有請輸出其中一種安排方式。 刪位數的問題 ( TIOJ 1397 ) 給你一個 n 位數的正整數 A，請問刪除其中 k 位數 ( k n )、將剩下的數字依序合併形成一個新的正整數B，B的最小可能值是多少？請注意，A和B的首位都不