鞋匠有 𝑁 件工作要完成。他每天只能做一件工作。並且他知道這些工作分別要幾個工作天才能完成。另外,他也知道每個工作被延誤一天所需被罰的罰金。延誤的天數為從今天算起到該工作開始的那天 (所以只有第一件工作沒有罰金)。
以第一組測試資料為例說明:若工作的順序是 1 2 3 4,那罰金為:0×4 + 1000×3 + 4×2 + 6×5 = 3038。若工作的順序是 2 1 3 4,則罰金為:0×1000 + 1×4 + 4×2 + 6×5 = 42。所以第二種工作順序的罰金較少 (事實上也是最少)。
你的任務是寫一個程式幫助鞋匠找出完成這 𝑁 個工作的先後順序,使得罰金最少。
輸入的第一列有一個整數代表以下有幾組測試資料。
每組測試資料的第一列,含有一個整數 𝑁(1 ≤ 𝑁 ≤1000),代表鞋匠需完成的工作數。接下來的 𝑁 列每列有 2 個整數,分別代表該工作完成所需的天數以及延遲一天的罰金多少 (均大於等於 1,小於等於 1000)。
第一列和第一組測試資料間,以及各組測試資料間均有一空白列。請參考範例輸入。
對每組測試資料輸出一列,為這 𝑁 個工作的順序使得罰金最少。工作之間以一空白字元分隔。如果有不只一組答案,請輸出字典順序最小的那組。
各組測試資料間亦請輸出一空白列。請參考範例輸出。
2 4 3 4 1 1000 2 2 5 5 5 3 4 1 1000 8 8 2 2 5 6
2 1 3 4 2 1 5 3 4
Lucky貓 ★★★ 中 英
ID | User | Problem | Subject | Hit | Post Date |
41002 | joccc014@gma ... (czone) | a673 | 121 | 2024-06-23 13:43 | |
39998 | mu0975353917 ... (Moon Chan) | a673 | 214 | 2024-04-19 01:17 | |
26118 | moneymade (qqqqqqqqqqq) | a673 | 897 | 2021-07-17 09:51 |