a316: Q-4-6. 少林寺的自動寄物櫃(APCS201710)
標籤 : greedy
通過比率 : 25人/26人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-04-20 19:30

內容

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

輸入說明

輸入的第一行是物品件數N,N<1e5。

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

第三行有N個正整數,依序是各物品的取用次數f(1)、f(2)、…、f(N),重量與次數皆不超過1000,相鄰以空白間隔。

輸出說明

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

範例輸入 #1
3
3 4 5
1 2 3
範例輸出 #1
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
提示 :
標籤:
greedy
出處:
AP325 [管理者: ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」