FatMouse' Trade
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 25 Accepted Submission(s) : 1
Problem Description
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
Sample Input
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
Sample Output
13.333
31.500
这一题，WA了我24次，破记录了，。。。。其实从昨晚WA第一次开始，我就发现问题了。。。。主要是题目的一个小细节，即，输入的是非负数，。。这就表明，输入的数据可能为0 。。。
我一开始担心f[i]为0，这样的话，计算性价比的时候可能会出错，但最后事实证明，在double类型下，除数为0，性价比会得到一个很大的数字，，但不会错。。其原因可能在于double值的0会被当成一个小数来进行计算，这样就不用考虑f[i]值为0的情况了。。。这时就要考虑j[i]为0的情况了。。。如果j[i]为0，其性价比毫无疑问就是0；因此，在排序的时候就默认会排到最后，但为了防止最终会被计入，我做了一个判断，直接将其性价比定为-10，。。。还有就是要考虑两个都为0的情况。。。如果语句书写不当。。本应输出0.000，却很可能输出一个乱码数字，（原因是判断条件没做好，使得0 0参与了运算，使得double值出乱）。。。
最最难想到的一个测试数据就是m=0,n=1;j[i]=1;p[i]=0;这样标准输出应为1.000，因为虽然初始豆为0，但获得JAVA豆的牺牲值也为0，故在写代码的时候 一定要考虑初始豆为0，但牺牲值也为0的情况。。。
以下是AC代码。。。
#include <cstdio>
#include <cstring>
int main()
{
int j[2000],p[2000];
int n,m;
double v[2000];
while (scanf("%d%d",&m,&n))
{ memset(v,0,sizeof(v));
memset(j,0,sizeof(j));
memset(p,0,sizeof(p));
if (m==-1&&n==-1) break;
for (int i=0;i<n;i++)
{
scanf("%d%d",&j[i],&p[i]);
if (j[i]==0) {v[i]=-10;}
else
v[i]=j[i]*1.0/p[i]*1.0;
}
for (int q=0;v[q];q++)
for (int w=q+1;v[w];w++)
{ double temp;int te,tt;
if (v[q]<v[w])
{
temp=v[q];v[q]=v[w];v[w]=temp;
te=j[q];j[q]=j[w];j[w]=te;
tt=p[q];p[q]=p[w];p[w]=tt;
}
}
int t=0;
double s=0;
while (m>=0&&v[t]>0)
{
if (m>=p[t]) {s=s+j[t];m=m-p[t];t++;}
if (m<p[t]) {s=s+m*v[t];break;}
}
printf("%.3f\n",s);
}
return 0;
}
#include <cstring>
int main()
{
int j[2000],p[2000];
int n,m;
double v[2000];
while (scanf("%d%d",&m,&n))
{ memset(v,0,sizeof(v));
memset(j,0,sizeof(j));
memset(p,0,sizeof(p));
if (m==-1&&n==-1) break;
for (int i=0;i<n;i++)
{
scanf("%d%d",&j[i],&p[i]);
if (j[i]==0) {v[i]=-10;}
else
v[i]=j[i]*1.0/p[i]*1.0;
}
for (int q=0;v[q];q++)
for (int w=q+1;v[w];w++)
{ double temp;int te,tt;
if (v[q]<v[w])
{
temp=v[q];v[q]=v[w];v[w]=temp;
te=j[q];j[q]=j[w];j[w]=te;
tt=p[q];p[q]=p[w];p[w]=tt;
}
}
int t=0;
double s=0;
while (m>=0&&v[t]>0)
{
if (m>=p[t]) {s=s+j[t];m=m-p[t];t++;}
if (m<p[t]) {s=s+m*v[t];break;}
}
printf("%.3f\n",s);
}
return 0;
}