HDOJ-1009 FatMouse'Trade
897 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1009
# include <stdio.h>
# include <algorithm>
# define MAX 1010
using namespace std;
struct NODE
{
int j, f;
double avg;
}food[MAX];
int n, m;
int cmp(const NODE& a, const NODE& b)
{
return a.avg > b.avg;
}
int main()
{
while(scanf("%d %d", &m, &n) && m != -1 && n != -1)
{
for(int i = 0; i < n; i++)
{
scanf("%d %d",&food[i].f, &food[i].j);
food[i].avg = food[i].f * 1.0 / food[i].j;
}sort(food, food+n, cmp);
double ans = 0;
for(int i = 0; i < n; i++)
{
if(m > food[i].j)
{
ans += food[i].f;
m -= food[i].j;
}
else
{
ans += (m * 1.0 / food[i].j * food[i].f);
m = 0;
break;
}
}
printf("%.3lf
", ans);
}
return 0;
}