(贪心5.2.1)UVA 10026 Shoemaker's Problem(利用数据有序化来进行贪心选择)

/*
 * UVA_10026.cpp
 *
 *  Created on: 2013年10月10日
 *      Author: Administrator
 */#include <iostream>
#include <cstdio>
#include <algorithm>using namespace std;const int maxn = 1010;
struct job{
double a;
int num;
}p[maxn];bool cmp(job x, job y){
if(x.a > y.a || (x.a == y.a && x.num < y.num)){
return true;
}return false;
}int main(){
int t;
scanf("%d",&t);
int counter = 1;
while(t--){
int n;
scanf("%d",&n);int i;
for(i = 1 ; i <= n ; ++i){
double a1,a2;
scanf("%lf%lf",&a1,&a2);
p[i].a = a2/a1;
p[i].num = i;
}sort(p+1,p+1+n,cmp);if(counter > 1){
printf("\n");
}
for(i = 1 ; i < n ; ++i){
printf("%d ",p[i].num);
}printf("%d\n",p[n].num);counter++;
}return 0;
}