(贪心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;}