hdu 1009 FatMouse' Trade

简单贪心.... 需要注意的是数据是非负,所以有0的情况要考虑周全,基本都要特殊处理。 多WA了三次,不知道为什么交C++可以过,交G++就不行。

 1    
 2    /* ***********************************************
 3    Author :111qqz
 4    Created Time :2016年02月19日 星期五 16时38分28秒
 5    File Name :code/hdu/1009.cpp
 6    ************************************************ */
 7    
 8    #include <iostream>
 9    #include <cstring>
10    #include <algorithm>
11    #include <cstdio>
12    #include <iomanip>
13     
14    using namespace std;
15     
16    int main()
17    {
18        int  m,n,f[1500],j[1500];
19        double scale[1500];
20        double ans,sum;
21        while(scanf("%d %d",&m,&n)!=EOF&&(m!=-1))
22        {  ans=0;
23          //  if (m==0)
24             memset(scale,0,sizeof(scale));
25             memset(f,0,sizeof(f));
26             memset(j,0,sizeof(j));
27           //  bool flag=false;
28           for (int i=1;i<=n;i++)
29            {
30                scanf("%d %d",&j[i],&f[i]);
31                if (f[i]!=0)
32                scale[i]=(double)j[i]*1.0/f[i];
33                else if (j[i]!=0)
34                {
35                      ans=ans+j[i];
36     
37                }
38            }
39           // if (flag) {cout<<fixed<<setprecision(3)<<ans<<endl;continue;}
40            for (int i=1;i<=n-1;i++)
41              for (int k=i+1;k<=n;k++)
42              if (scale[i]<scale[k])
43            {
44                swap(scale[i],scale[k]);
45                swap(j[i],j[k]);
46                swap(f[i],f[k]);
47            }
48            sum=0;
49           int i=1;
50            while (m>=sum&&i<=n)
51            {
52              ans=ans+j[i];
53              sum=sum+f[i];
54              i++;
55            }
56            i--;
57            ans=ans-j[i];
58            sum=sum-f[i];
59            ans=ans+(m-sum)*scale[i];
60            cout<<fixed<<setprecision(3)<<ans<<endl;
61     
62     
63        }
64        return 0;
65    }
66    
67