w22116972
3/28/2014 - 4:30 PM

UVA 10026

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;
}