嵩山磨劍坊接了 $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$。
4 1 4 5 6 1 3 4 7
145
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||