主題
題目連結：
題目大意：
第一列給定一正整數，代表測試資料的組數。
每組測資前會有一空白列，測資的第一列給定一正整數 N （1 ≦ N ≦ 1000），代表鞋匠有 N 件工作要做，編號為 1 ～ N 。接著的 N 列輸入，每列有兩正整數（皆介於 1 ～ 1000 之間），依序代表此工作所需的工作天數以及每延遲一天須付的罰金金額。
每個工作計算延遲天數是以現在這天開始，到此工作開始（一旦開始就會一次做完）的那天為止。因此只有第一個工作不須付罰金。罰金的總額即為延遲天數 × 延期一天的罰金。
求這 N 個工作應以什麼順序去做，才可使罰金總額最少？請將工作順序輸出至一列，每個工作的編號彼此應以一個空格字元分隔。每筆測試資料的輸出之間也應空出一空白列。若答案有多組可能，請輸出字典序最小的那組。
範例輸入：
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
解題思維：
假設兩個工作之編號為 a 和 b ，各自所需的工作天、罰金分別為 Da 、 Db 、 Fa 、 Fb 並假設已工作了 X 天（前面的工作之天數總和）。
如果工作 a 在前，則目前罰金額度應為
（X） × Fa ＋ （ Da ＋ X ） × Fb
若工作 b 在前，則為
（X） × Fb ＋ （ Db ＋ X ） × Fa
可以看到上面兩個式子皆有 X × Fa ＋ X × Fb ，將此值從上面二式去除後分別變為
Da × Fb
以及
Db × Fa
因為要使罰金盡可能地少，因此：
當 Da × Fb ＜ Db × Fa 時，代表工作 a 應在前面。
當 Da × Fb ＞ Db × Fa 時，代表工作 b 應排於前。
當 Da × Fb ＝ Db × Fa 時，看 a 、 b 何者為較小的編號，較小的編號須排前面。因為字典序須最小。
所以，整個題目實際上是一個簡單的排序問題。而排序的依據即如上。排完之後，從排定的第一個工作到最後一個，依序輸出它們原本的工作編號即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
