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\n", ans);
} return 0;
}