a673. 10026 - Shoemaker's Problem
Tags :
Accepted rate : 380人/407人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-13 15:53

Content

鞋匠有 𝑁 件工作要完成。他每天只能做一件工作。並且他知道這些工作分別要幾個工作天才能完成。另外,他也知道每個工作被延誤一天所需被罰的罰金。延誤的天數為從今天算起到該工作開始的那天 (所以只有第一件工作沒有罰金)。

以第一組測試資料為例說明:若工作的順序是 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。所以第二種工作順序的罰金較少 (事實上也是最少)。

你的任務是寫一個程式幫助鞋匠找出完成這 𝑁 個工作的先後順序,使得罰金最少。

Input

輸入的第一列有一個整數代表以下有幾組測試資料。

每組測試資料的第一列,含有一個整數 𝑁(1 ≤ 𝑁 ≤1000),代表鞋匠需完成的工作數。接下來的 𝑁 列每列有 2 個整數,分別代表該工作完成所需的天數以及延遲一天的罰金多少 (均大於等於 1,小於等於 1000)。

第一列和第一組測試資料間,以及各組測試資料間均有一空白列。請參考範例輸入。

Output

對每組測試資料輸出一列,為這 𝑁 個工作的順序使得罰金最少。工作之間以一空白字元分隔。如果有不只一組答案,請輸出字典順序最小的那組。

各組測試資料間亦請輸出一空白列。請參考範例輸出。

Sample Input #1
2

4
3 4
1 1000
2 2
5 5

5
3 4
1 1000
8 8
2 2
5 6
Sample Output #1
2 1 3 4

2 1 5 3 4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

Lucky貓 ★★★ 中 英

Tags:
出處:
UVa10026 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
41002 joccc014@gma ... (czone) a673
PYthon 想法&思路
26 2024-06-23 13:43
39998 mu0975353917 ... (Moon Chan) a673
解題想法
101 2024-04-19 01:17
26118 moneymade (qqqqqqqqqqq) a673
hint
821 2021-07-17 09:51