a673. 10026 - Shoemaker's Problem
標籤 :
通過比率 : 402人/432人 ( 93% ) [非即時]
評分方式:
Tolerant

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

內容

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

以第一組測試資料為例說明:若工作的順序是 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)。

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

輸出說明

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

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

範例輸入 #1
2

4
3 4
1 1000
2 2
5 5

5
3 4
1 1000
8 8
2 2
5 6
範例輸出 #1
2 1 3 4

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

Lucky貓 ★★★ 中 英

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41002 joccc014@gma ... (czone) a673
PYthon 想法&思路
104 2024-06-23 13:43
39998 mu0975353917 ... (Moon Chan) a673
解題想法
195 2024-04-19 01:17
26118 moneymade (qqqqqqqqqqq) a673
hint
889 2021-07-17 09:51