d047: Q-4-6. 少林寺的自動寄物櫃(APCS201710)
Tags : greedy
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-09 17:30

Content

少林寺的自動寄物櫃系統存放物品時,是將 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 的能量消耗是 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。

Input

輸入的第一行是物品件數 N,N<1e5。第二行有 N 個正整數,依序是各物

品的重量 w(1)、w(2)、…、w(N)。第三行有 N 個正整數,依序是各物品的取用次數

f(1)、f(2)、…、f(N),重量與次數皆不超過 1000,相鄰以空白間隔。

Output

輸出最小能量消耗值。答案不超過 1e18。

Sample Input
3
3 4 5
1 2 3
Sample Output
19
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :

若有兩物A, B,能列出A上B下及B上A下分別的成本嗎?

Tags:
greedy
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」