uva 10026 Shoemaker's Problem

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=967

对价钱与天数比例排序，贪心即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 2000
 5 using namespace std;
 6 
 7 int n;
 8 struct node
 9 {
10     int num;
11     double pay;
12     int d;
13     bool operator <(const node &a)const
14     {
15         return (pay>a.pay)||(pay==a.pay&&num<a.num);
16     }
17 }p[maxn];
18 
19 int main()
20 {
21     int t;
22     scanf("%d",&t);
23     while(t--)
24     {
25         scanf("%d",&n);
26         for(int i=1; i<=n; i++)
27         {
28             int x,y;
29             scanf("%d%d",&x,&y);
30             p[i].num=i;
31             p[i].pay=(double)(y*1.0/x);
32             p[i].d=x;
33         }
34         sort(p+1,p+1+n);
35         for(int i=1; i<=n; i++)
36         {
37             if(i==1)
38             {
39                 printf("%d",p[i].num);
40             }
41             else printf(" %d",p[i].num);
42         }
43         printf("
");
44         if(t) printf("
");
45     }
46 }

View Code