UVA 10026
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
#include <iterator>
using namespace std;
/*
這題的概念是說,如果今天不做此項工作,則必須把不做的天數*這工作的罰金
然後取罰金最小的組合
由於需要記錄編號 天數 罰金
因此用class
*/
class Job{
public:
int id,day,fine;
Job(){id=day=fine=0;}
bool operator < ( const Job& job2)const{
if (day*job2.fine == fine*job2.day)
return id < job2.id;
else
return (day*job2.fine) < (fine*job2.day);
}
// 因為cmp回傳的是bool
// 當兩者的值相同時,以編號來決定順序
// 不相同時,直接回傳比較式即可得到true or false
};
int main(int argc, const char * argv[])
{
int cases;
cin >> cases;
for (int j=0; j<cases; j++) {
if (j)
cout <<endl;
int n;
cin >> n;
vector<Job> jobs(n);
for (int i=0; i<n; i++) {
cin >> jobs[i].day >> jobs[i].fine;
jobs[i].id = i+1;
}
// 直接對job做排序 由於先前已經有使用operator定義,所以這邊不需要針對compare
sort(jobs.begin() , jobs.end());
for (int i=0; i<n; i++) {
if (i)
cout << " ";
cout << jobs[i].id;
}
cout << endl;
}
return 0;
}