Note: This article is available in Chinese only. 本文暂无英文版本。
View original
简单贪心…. 需要注意的是数据是非负，所以有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 }