A shoemaker has N orders from customers which he must satisfy. The shoemaker can
work on only one job in each day, and jobs usually take several days. For the ith job,
the integer Ti (1 ≤ Ti ≤ 1, 000) denotes the number of days it takes the shoemaker to
finish the job.
But popularity has its price. For each day of delay before starting to work on the ith
job, the shoemaker has agreed to pay a fine of Si (1 ≤ Si ≤ 10, 000) cents per day. Help
the shoemaker by writing a program to find the sequence of jobs with minimum total fine.
Input
The input begins with a single positive integer on a line by itself indicating the number
of the test cases, followed by a blank line. There is also a blank line between two
consecutive cases.
The first line of each case contains an integer reporting the number of jobs N, where
1 ≤ N ≤ 1, 000. The ith subsequent line contains the completion time Ti and daily
penalty Si for the ith job.
Output
For each test case, your program should print the sequence of jobs with minimal fine.
Each job should be represented by its position in the input. All integers should be placed
on only one output line and each pair separated by one space. If multiple solutions are
possible, print the first one in lexicographic order.
The output of two consecutive cases must be separated by a blank line.
Sample Input
1
4
3 4
1 1000
2 2
5 5
Sample Output
2 1 3 4
На ум приходит только одно возможное решение - перебрать всевозможные комбинации, что не приемлимо, так как заказов может быть 1000, программа не справится с таким огромным количеством операций.
Есть подсказка использовать сортировку, возможно по нескольким полям
Does it help to sort jobs by their length, or by their penalty, or both?
Чего-то подсказка не очень-то и помогает мне.
Есть идеи?
