貪婪(Greedy)演算法

內容 ：

有一個叫做傻人國的國家，他們的國會要召開新會期了。國會總共有N個議員。根據現行的法規議員們被分在不同的委員會（每個議員僅能待在一個委員 會），且每個委員會的人數均不相同。每天每一個委員會都需推派一名代表參加協調會，而且協調會每天的組成都需不同。國會只有在以上的條件成立之下才能運 作。

你的任務是寫一個程式來幫這些議員分組（總共分多少組，每個組多少人），使得國會能夠運作的天數最大。

輸入說明 ： 

輸入的第一列有一個整數代表以下有多少組測試資料。

每組測試資料一列，含有1個整數 N（5 <= N <= 1000）。

第一列與第一組測試資料以及各組測試資料間均有一空白列，請參考Sample Input。

輸出說明 ： 

對每組測試資料輸出一列，包含委員會的數目以及各委員會的人數，使得國會能夠運作的天數最大。各委員會輸出的順序按人數由小到大輸出。以第一組測試資料為例說明：31個委員共被分成6組，各組人數分別為2、3、5、6、7、8。

各組測試資料間亦請輸出一空白列，輸出格式請參考Sample Output。

範例輸入 ： 

3

31

5

8

範例輸出 ：

2 3 5 6 7 8

2 3

3 5

提示 ： 

* Luck 貓翻譯

出處 ： 

ACM 668

解題策略

貪婪演算法(Greedy)

將n切割成不同數字，且各數字的積最大 

step1  k+1無法達到則結束

       表示將n先分給2,3,4,5, ... ,k，若n-(2+3+...+k)<k+1則結束 

step2  將剩餘n-(2+3+...+k)由k開始平均分給

       k,k-1,k-2..2用完為止

step3  若還有剩餘，也只會剩一個，分給k(最後一位)

問題描述

全國最大的便利商店正在舉行集點數換獎品的活動,任何參與者皆可以依據其收集到的貼紙點數,換得相對應的獎品。根據該活動的活動辦法,我們知道點數越高所能換得的獎品價值越高;但是,每次兌換獎品時,只限使用一張集點卡上所收集到的點數,不能合併多張集點卡的點數使用。

小智目前手上共有 n 張集點卡,為了換取最高價值的獎品,決定尋求科技公司的協助,將這些集點卡上的所有點數合併到單一集點卡上。然而,這家科技公司的服務有兩項規定:

1) 一次只能合併兩張集點卡,

2) 每次進行合併時,需收取和合併後點數相同數目的手續費。

例如,若小智手上有 3 張集點卡,上面的點數分別是 1, 3, 8。若小智第一次合併點數為 1 和 8 的集點卡,則合併後的新集點卡點數為 9,同時必須付 9 元的手續費;接著,小智要合併點數為 3 和 9 的集點卡,合併後的點數為 12,且手續費為 12 元。因此,兩次合併的手續費總和為 9 + 12 = 21 元。但是,若小智第一次合併點數為 1 和 3 的集點卡,則合併後的新集點卡點數為 4,且手續費為 4 元;接著,小智合併點數為 4 和8 的集點卡,合併後的點數為 12,且手續費為 12 元。因此,兩次合併的手續費總和為 4+ 12 = 16 元。

小智發現不同的合併順序,並不會影響最後合併完成時集點卡上的總點數,但卻會影

響合併所需的手續費。請你幫忙小智計算合併 n 張集點卡的最低手續費。

輸入格式

輸入的第一行有一個整數 n,代表需要合併的集點卡張數;第二行有 n 個以空白符號相間隔的正整數,分別代表這 n 張集點卡原有收集到的點數。同時,輸入資料中,每一張集點卡上原有收集到的點數,皆為小於或等於 1,000 的正整數。

輸出格式

請根據輸入的資料,輸出合併這 n 張集點卡所需最低手續費。

輸入範例 1

3

1 3 8

輸出範例 1

16

輸入範例 2

4

8 3 5 1

輸出範例 2

30

解題策略

Huffman編碼

內容 ：

有一間工廠生產的東西, 被包裝在相同高度 h 的正方形容器內, 但其面積大小分別有:1*1, 2*2, 3*3, 4*4, 5*5, 6*6等六種尺寸。這些產品總是用高度為h，面積為6*6的箱子打包後寄給客戶。因為成本關係，當然希望將客戶所訂購的產品放在最少的箱子裡寄出。請你寫 一個程式找出寄送這些產品最少需要多少個箱子，這可以使工廠節省下不少錢。

輸入說明 ：

每組測試資料一列（就是一份訂單），含有6個整數。分別代表1*1到6*6產品的數目。若此6個整數均為0代表輸入結束。

輸出說明 ：

對每一組測試資料，輸出寄送這些產品最少需要多少個箱子。

範例輸入 ：

0 0 4 0 0 1

7 5 1 0 0 0

0 0 0 0 0 3

79 96 94 30 18 14

53 17 12 98 76 54

83 44 47 42 80 3

15 26 13 29 42 40

41 61 36 90 54 66

0 0 0 0 0 0

範例輸出 ：

2

1

3

86

231

137

115

219

提示 ：

* Luck 貓翻譯

出處 ：

ACM 311

解題策略

貪婪(Greedy)

處理6x6

處理5x5 剩餘的給1x1

處理4x4 剩餘的給2x2與1x1

處理3x3 剩餘的給2x2與1x1

處理2x2 剩餘的給1x1

處理1x1

問題描述

某個自動化系統中有一個存取物品的子系統,該系統是將 N 個物品堆在一個垂直的貨架上,每個物品各佔一層。系統運作的方式如下:每次只會取用一個物品,取用時必須先將在其上方的物品貨架升高,取用後必須將該物品放回,然後將剛才升起的貨架降回原始位置,之後才會進行下一個物品的取用。

每一次升高某些物品所需要消耗的能量是以這些物品的總重來計算,在此我們忽略貨架的重量以及其他可能的消耗。現在有 N 個物品,第 i 個物品的重量是 w(i)而需要取用的次數為 f(i),我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。舉例來說,有兩個物品 w(1)=1、w(2)=2、f(1)=3、f(2)=4,也就是說物品 1 的重量是 1 需取用 3次,物品 2 的重量是 2 需取用 4 次。我們有兩個可能的擺放順序(由上而下):

 (1,2),也就是物品 1 放在上方,2 在下方。那麼,取用 1 的時候不需要能量,而每次取用 2 的能量消耗是 w(1)=1,因為 2 需取用 f(2)=4 次,所以消耗能量數為w(1)*f(2)=4。

 (2,1),也就是物品 2 放在 1 的上方。那麼,取用 2 的時候不需要能量,而每次取用1的能量消耗是w(2)=2,因為1需取用f(1)=3次,所以消耗能量數=w(2)*f(1)=6。

在所有可能的兩種擺放順序中,最少的能量是 4,所以答案是 4。再舉一例,若有三物品而 w(1)=3、w(2)=4、w(3)=5、f(1)=1、f(2)=2、f(3)=3。假設由上而下以(3,2,1)的順序,此時能量計算方式如下:取用物品 3 不需要能量,取用物品 2 消耗 w(3)*f(2)=10,取用物品 1 消耗(w(3)+w(2))*f(1)=9,總計能量為 19。如果以(1,2,3)的順序,則消耗能量為3*2+(3+4)*3=27。事實上,我們一共有 3!=6 種可能的擺放順序,其中順序(3,2,1)可以得到最小消耗能量 19。

輸入格式

輸入的第一行是物品件數 N,第二行有 N 個正整數,依序是各物品的重量 w(1)、w(2)、...、w(N),重量皆不超過 1000 且以一個空白間隔。第三行有 N 個正整數,依序是各物品的取用次數 f(1)、f(2)、...、f(N),次數皆為 1000 以內的正整數,以一個空白間隔。

輸出格式

輸出最小能量消耗值,以換行結尾。所求答案不會超過 63 個位元所能表示的正整數。

範例一(第 1、3 子題):輸入

2

20 10

1 1

範例一:正確輸出

10

範例二(第 2、4 子題):輸入

3

3 4 5

1 2 3

範例二:正確輸出

19

解題策略

貪婪(Greedy)

先找出物品的順序，若物品a與b，先以a.w*b.f < b.w*a.f排序，也就是本身重量(a.w)與對方頻率(b.f)相乘的值越小的物品優先放在上層，有了順序就可以計算最小消耗能量。

參考資料

https://henrybear327.github.io/CodingNotes/contest/apcs/1061028/

有一個長度為 L 的長條型的林場，N 棵樹種在一排，現階段砍樹必須符合以下的條件：「讓它向左或向右倒下，倒下時不會超過林場的左右範圍之外，也不會壓到其它尚未砍除的樹木。」你的工作就是計算能砍除的樹木。

 若 ci 代表第 i 棵樹的位置座標，hi 代表高度。向左倒下壓到的範圍為 [ci−hi,ci]，而向右倒下壓到的範圍為 [ci,ci+hi]。 如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。 我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。

無論砍樹的順序為何，最後能砍除的樹木是相同的。

輸入說明

第一行為正整數 N 以及一個正整數 L，代表樹的數量與林場右邊界的座標。N≤10^5，L≤10^9 。 

第二行有 N 個正整數依序代表這 N 棵樹的座標，座標是從小到大排序的，所有座標不超過 L。

第三行有 N 個正整數依序代表樹的高度，所有樹高都不超過 10^9。 

本題包含三個子題組，每個子題組配分如下： 

第 1 子題組共 20 分： N≤10 

第 2 子題組共 40 分： N≤1000 

第 3 子題組共 40 分： 無額外限制。

輸出說明

輸出共有兩行，第一行輸出能被砍除之樹木數量，第二行輸出能被砍除之樹木中最高的高度，如果無法砍除任何一棵樹，則最高高度輸出 0。

輸入範例1

6 140

10 30 50 70 100 125

30 15 55 10 55 25

輸出範例1

4 

30

輸入範例2

1 10

5

6

輸出範例2

0

0

解題策略

由左到右掃描所有樹，將不可移除的樹加入堆疊。考慮新的樹，如果堆疊內有可以移除(向右倒下，連鎖反應)的樹就移除，接著檢查新的樹是否可以移除(向左倒下，此時向右倒下可以暫時不考慮)，可以就移除，否則加入堆疊，直到檢查所有樹為止。

有 n 台機器排成一直線, 每一個機器都有一個數值 t[i], 代表該台機器要產出一單位的資料需要 t[i] 單位的時間 接下來有 m 個工作要完成, 每一個工作都需要位置在 [l[i],r[i]] 的機器各生產出 w[i] 單位資料 現在你可以調換 n 台機器的順序, 目標是使得這 m 個工作做完的總時間要最小

輸入說明

先輸入兩個正整數 n 和 m 代表有 n 台機器和 m 個工作 接下來有 m 行, 每行有三個正整數 l[i], r[i] 和 w[i] 代表第 i 個工作需要編號從 l[i] 到 r[i] 的機器完成, 並且需要各產生出 w[i] 單位的資料 最後一行包含 n 個正整數 t[1],t[2],⋯t[n] 

數字範圍 

1≤n,m≤200000 

1≤w[i]≤100 

1≤t[i]≤100 

1≤l[i]≤r[i]≤n

輸出說明

輸出最小的總花費時間

輸入範例

5 1

2 4 1

1 2 3 4 5

10 3

2 5 6

3 6 4

7 8 1

1 2 3 4 5 6 7 8 9 10

輸出範例

6

117

解題策略

差分、排序、貪婪

第一組測資

5 1

2 4 1

1 2 3 4 5

生產資料量  1 1 1

時間           1 2 3 4 5

機器              1 2 3

          1*1+1*2+1*3=6

第二組測資

10 3

2 5 6

3 6 4

7 8 1

1 2 3 4 5 6 7 8 9 10

生產資料量     6 10 10 10  4  1  1

時間             1 2  3   4   5   6   7  8

機器                 4 1   2    3   5  6  7

          10*1 + 10*2 + 10*3 + 6*4 + 4*5 + 1*6 + 1*7 =117

使用差分與累加計算每一個時間點的生產資料量，生產資料量最大的時間點安排t[i]最小的機器，將生產資料量由大到小排序，t[i]由小到大排序，依序相乘累加。