回分類題庫
d157: 2010 SIG WINTER H - 胖達的桃花運
出處:

Difficulity : 1
Accepted : 15 Times | Submit :42 Times | Clicks : 1429
Accepted : 10 Users | Submit : 11 Users | Accepted rate : 91%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2010-02-09 02:43

Content :

胖達有N個女孩子要約會。他每天只能跟其中一個女孩出遊。並且他知道每次出遊都要出去玩上好幾天才會回來。另外,他也知道其他女孩子被冷落一天分別會產生不同量的忌妒心。冷落的天數為從今天算起到陪那位女孩出遊開始的那天(所以只有和第一個女孩出遊不會產生忌妒心)。

以第一組測試資料為例說明:若與女孩出遊的順序是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。所以第二種出遊的順序產生的總忌妒心量較少(事實上也是最少)。

你的任務是寫一個程式幫助胖達找出和這N個女孩出遊的先後順序,讓女孩們感到開心(也就是使得女孩們產生的總忌妒心最少)。

Input :

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

每組測試資料的第一列,含有一個整數N(1 <= N <=1000),代表胖達要和幾位女孩出遊。接下來的N列每列有2個整數,分別代表和這位女孩出遊的天數以及讓這位女孩等待一天所產生的忌妒感(均大於等於1,小於等於1000)。

第一列和第一組測試資料間,以及各組測試資料間均有一空白列。請參考Sample Inout。

Output :

對每組測試資料輸出一列,為和N為女孩出遊的順序使得胖達獲得最佳好評(女孩們的總忌妒心量最少)。每為女孩之間以一空白字元分隔。如果有不只一組答案,請輸出字典順序最小的那組。

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

Sample Input :

2

4
3 4
1 1000
2 2
5 5

5
3 4
1 1000
8 8
2 2
5 6 

Sample Output :

2 1 3 4

2 1 5 3 4

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
37185. nothinglo (90 ms , 428KB)
37174. cp99303052 (92 ms , 440KB)
37183. MK (96 ms , 432KB)
18257. aytawgf (102 ms , 488KB)
37184. MK (108 ms , 438KB)
54730. ag100 (42 ms , 328KB)
18741. yuhanlyu (46 ms , 364KB)
54729. ag100 (78 ms , 336KB)
54728. ag100 (82 ms , 330KB)
63312. nwgs524513cja (748 ms , 23626KB)
63311. nwgs524513cja (810 ms , 23330KB)

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡