時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
鞋匠有 N 份工作，一次只能做一份。第 i 份需要 Ti 天，開始這份工作之前每延遲一天就須付 Si 分罰款。安排工作順序，使總罰款最小；若有多個最佳順序，選工作編號序列字典序最小者。工作編號按輸入順序從 1 開始。
輸入格式
第一行測試筆數，各組間有空白行。每組先給 N（1 ≤ N ≤ 1000），再給 N 行 Ti、Si，其中 1 ≤ Ti ≤ 1000，1 ≤ Si ≤ 10000。
輸出格式
每組輸出一行工作編號，數字間一個空白。兩組輸出間留一空白行。
題目來源：UVa 10026 — Shoemaker’s problem，CPE 歷屆試題。 原題：https://onlinejudge.org/external/100/10026.pdf
範例測資
範例輸入 1
1 4 3 4 1 1000 2 2 5 5
範例輸出 1
2 1 3 4
請先登入後再提交程式碼
討論與題解
載入討論區…