嵩山磨劍坊的問題 (AP325 P-4-5)

嵩山磨劍坊接了 \(n\) 筆磨劍工作，磨劍師傅每次只能磨一把劍。除了每把劍各有所需的時間之外，每件工作的重要性也不同。假設第 \(i\) 筆訂單需要的時間是 \(t[i]\)，而重要性是 \(w[i]\)。磨劍坊的計價方式是：每件工作都已經先收了一筆款項，假設第 \(i\) 筆訂單在時間 \(f\) 時完成，則需要扣款 \(f \times w[i]\)，現在希望將 \(n\) 筆磨劍工作安排最好的順序，使得扣款總額越小越好。嵩山派掌門左冷禪是非常嚴厲的老闆，希望你能幫磨劍師傅找出最好的順序以免他遭到處罰。

舉例來說，如果有四把劍，磨劍需要的時間分別是 \(t = (1, 4, 5, 6)\)，而重要性依序是 \(w = (1, 3, 4, 7)\)。如果依訂單編號順序 \((1, 2, 3, 4)\) 來磨，也剛好是工作時間由短到長的順序，每件工作的完成時間依序是 \((1, 5, 10, 16)\)，扣款總額是 \(1 \times 1 + 5 \times 3 + 10 \times 4 + 16 \times 7 = 168\)。如果依照訂單編號順序 \((4, 1, 3, 2)\) 來磨，則 \(t\) 與 \(w\) 重新排列後分別是 \(t = (6, 1, 5, 4)\)，\(w = (7, 1, 4, 3)\)，完工時間是 \((6, 7, 12, 16)\)，扣款總額是 \(6 \times 7 + 7 \times 1 + 12 \times 4 + 16 \times 3 = 145\)。這是這一題 \(24\) 種排列中最好的解。

輸入格式

輸入的第一行是工作數 \(n\)。第二行有 \(n\) 個正整數，依序是各訂單所需時間 \(t[1]\)、\(t[2]\)、…、\(t[n]\)。第三行有 \(n\) 個非負整數，依序是各訂單的重要性 \(w[1]\)、\(w[2]\)、…、\(w[n]\)，相鄰以空白間隔。

限制

• \(1 \le n < 10^5\)。
• \(1 \le t[i] \le 1000\)，\(0 \le w[i] \le 1000\)。
• 答案不超過 \(10^{18}\)。

輸出格式

輸出最小的扣款總額。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

4
1 4 5 6
1 3 4 7

範例輸出

145

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 4 章 P-4-5，第 118 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。