Problem Description
小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆。
仓库有N个房间；
第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；
老鼠不必交换该房间所有的五香豆，换句话说，它可以用 F[i] a% 磅的猫粮去换取J[i] a%磅的五香豆，其中a是一个实数。
现在，请帮忙计算一下，小老鼠最多能够得到多少磅的五香豆？
Input
输入包含多组测试用例。
每组测试数据首先一行是2个非负整数M和N，接着的N行，每行分别包含2个非负整数J[i]和F[i]。
输入数据以两个-1结束。
题目保证所有的数据不超过1000.
Output
请计算并输出小老鼠最多能够得到的五香豆数量。
每组数据输出一行，保留3位小数。
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
贪心
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct node
{
double j,f,s;
}t[N];
bool cmp(node T1,node T2)
{
return T1.s>T2.s;
}
int main()
{
double m;
int n;
while(cin>>m>>n,~n)
{
for(int i=0;i<n;++i)
{
cin>>t[i].j>>t[i].f;
t[i].s=t[i].j/t[i].f;
}
sort(t,t+n,cmp);
double res=0;
int i=0;
while(fabs(m)>1e-5&&i<n)//注意这里的限制条件必须要加上i
//否则会将之前没有清空的数组一起运算
{
if(t[i].f<=m)
{m-=t[i].f;res+=t[i++].j;}
else
{res+=m*t[i++].s;m=0;}
}
res=round(res*1000)/1000.0;
printf("%.3lf\n",res);
}
}