10610第4題物品堆疊
作業上傳：http://203.68.236.9/problem/c0301
zerojudge 網址 https://zerojudge.tw/ShowProblem?problemid=c471
出處：APCS
問題描述
某個自動化系統中有一個存取物品的子系統,該系統是將 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/
參考程式碼