算法提高 快乐司机

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<iostream>
 4 using namespace std;
 5 struct node{
 6     int g,p;
 7     double ave;
 8 } s[10010];
 9 
10 int main()
11 {
12     int n,w;
13     double sum=0;
14     scanf("%d%d",&n,&w);
15     for(int i=0;i<n;i++)
16         scanf("%d%d",&s[i].g,&s[i].p);
17     for(int i=0;i<n;i++)
18         s[i].ave=(double) s[i].p/s[i].g;
19     //for(int i=0;i<n;i++)
20     //    printf("%d %d %f\n",s[i].g,s[i].p,s[i].ave);
21     for(int i=0;i<n-1;i++)
22     {
23         for(int j=i;j<n;j++)
24         {
25             if(s[i].ave<s[j].ave)
26             {
27                 int t,x;
28                 double av;
29                 
30                 
31             av=s[i].ave;    s[i].ave=s[j].ave; s[j].ave=av;
32                 
33             
34             t=s[i].p;       s[i].p=s[j].p;  s[j].p=t;
35                 
36             x=s[i].g;    s[i].g=s[j].g;    s[j].g=x;    
37                 
38             }
39         }
40     }
41     //for(int i=0;i<n;i++)
42     //    printf("%d %d %f\n",s[i].g,s[i].p,s[i].ave);
43      int i;
44      for(i=0;i<n;i++)
45      {
46          if(w>=s[i].g)
47          {
48              sum+=s[i].p;
49              w-=s[i].g;    
50         }
51         else
52         break;
53     }
54     if(w==0)
55     ;
56     else
57     {
58         sum=sum+(w*s[i].ave);
59     }
60     printf("%.1f\n",sum);
61  
62         
63 }