Hdu 1009 FatMouse' Trade解题报告

/**/ /*
input:
53
72
43
52
output
13.333
5个猫食，3个房间，第1个房间2个猫食换7个JavaBean，第2个房间3个猫食换4个JavaBean，第3个房间2个猫食换5个JavaBean；
最大量的JavaBean是7+5+(1/3)*4=13.333。
简单的贪心策略:每次以最小量的猫食换最大量的JavaBean，即每次取(J[i]/F[i])最大的J[i]将使换得的JavaBean量最大。
*/

#include < algorithm >
#include < iostream >
#include < vector >
using namespace std;

struct JavaBeanCaCatFood
... {
int JavaBean,CatFood;
} ;

bool cmp(JavaBeanCaCatFooda,JavaBeanCaCatFoodb)
... {
return ( double )a.JavaBean / a.CatFood > ( double )b.JavaBean / b.CatFood;
}

bool run() ... {
int n,m;
cin >> m >> n;
if (m ==- 1 && n ==- 1 ) return false ;

vector < JavaBeanCaCatFood > JavaBeanCaCatFood(n);

int i;
for (i = 0 ;i < n;i ++ )cin >> JavaBeanCaCatFood[i].JavaBean >> JavaBeanCaCatFood[i].CatFood;

sort(JavaBeanCaCatFood.begin(),JavaBeanCaCatFood.end(),cmp);

double s = 0 ,t = 0 ;

for (i = 0 ;i < n;i ++ )
... {
if (m >= JavaBeanCaCatFood[i].CatFood) // i房间的能全换
... {
m -= JavaBeanCaCatFood[i].CatFood;
t += JavaBeanCaCatFood[i].JavaBean;
}
else
... {
t += JavaBeanCaCatFood[i].JavaBean * (( double )m / JavaBeanCaCatFood[i].CatFood); // 剩下不够全换
break ;
}
}

printf( " %.3lf " ,t);

return true ;
}

int main() ... {
while (run());
return 0 ;
}