a315:
P-4-5. 嵩山磨劍坊的問題-加權最小完成時間
內容
嵩山磨劍坊接了n筆磨劍工作，磨劍師傅每次只能磨一把劍。
除了每把劍各有所需的時間之外，每件工作的重要性也不同。
假設第i筆訂單需要的時間是t[i]，而重要性是w[i]。
磨劍坊的計價方式是：每件工作都已經先收了一筆款項，假設第i筆訂單在時間f時完成，則需要扣款f*w[i]，現在希望將n筆磨劍工作安排最好的順序，使得扣款總額越小越好。
嵩山派掌門左冷禪是非常嚴厲的老闆，希望你能幫磨劍師傅找出最好的順序以免他遭到處罰。
舉例來說，如果有四把劍，磨劍需要的時間分別是t=(1,4,5,6)，而重要性依序是w=(1,3,4,7)。
如果依訂單編號順序(1,2,3,4)來磨，也剛好是工作時間由短到長的順序，每件工作的完成時間依序是(1,5,10,16)，扣款總額是1*1 + 5*3 + 10*4 + 16*7 = 168。
如果依照訂單編號順序(4,1,3,2) 來磨,則t與w重新排列後分別是t=(6,1,5,4)，w=(7,1,4,3)。完工時間是(6,7,12,16)，扣款總額是6*7 + 7*1 + 12*4 + 16*3 = 145。
這是這一題24種排列中最好的解。
輸入說明
輸入的第一行工作數N，N<1e5。
第二行有N個正整數，依序是各訂單所需時間t[1]、t[2]、…、t[N]。
第三行有N個非負整數，依序是各訂單的重要性w[1]、w[2]、…、w[N]，時間與重要性皆不超過1000，相鄰以空白間隔。
輸出說明
輸出最小的扣款總額。 答案不超過1e18
範例輸入
#1
4 1 4 5 6 1 3 4 7
範例輸出
#1
145
測資資訊：
記憶體限制：
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
公開 測資點#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
提示 ：
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||