(贪心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("
");
		}
		for(i = 1 ; i < n ; ++i){
			printf("%d ",p[i].num);
		}

		printf("%d
",p[n].num);

		counter++;
	}

	return 0;
}