这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
AC了题目的心情总是格外的好。呵呵。
这个类型的贪心题算是经典的经典的。 题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1009
题意是用猫粮换javabean。可以按比例兑换(还有其他类型题目不能按比例换的,注意了)
思路:先j[i]/f[i]的比例进行由大到小的排序。然后依次减去f[i],获得值加上j[i]。这里要考虑几种情况。
1.M值减到一定程度后,不够换一个房间的的javabean,这里就只能把剩下的M按比例换了。
2.全部换完M还有多余的。剩余的就不管。(这里先没注意,只判断M是否小于0,结果 Output Limit Exceeded)
好了,剩下的就是贴代码了:
#include
#include
using namespace std;
// Author: Tanky Woo
// 31MS 212K 1174B
typedef struct TRADE{
int ji; // javabean
int fi; // cat food
double scale; // 比例
}TRADE;
TRADE trade[1000];
int M, N;
int cmp(TRADE a, TRADE b)
{
return (a.scale > b.scale); //从大到小
}
int main()
{
//freopen("input.txt", "r", stdin);
while(scanf("%d %d", &M;, &N;) && !(M == -1 && N == -1))
{
//printf("1\n");
memset(trade, 0, sizeof(trade));
for(int i = 0; i < N; ++i)
{
scanf("%d %d", ™[i].ji, ™[i].fi);
trade[i].scale = double(trade[i].ji)/trade[i].fi;
}
sort(trade, trade+N, cmp);
/*
for(int i = 0; i < N; ++i)
printf("%d %d %lf\n",trade[i].ji, trade[i].fi, trade[i].scale);
*/
int cnt = 0;
double sum = 0.0;
while(M > 0 && cnt < N)
{
if(M >= trade[cnt].fi)
{
sum += trade[cnt].ji;
M -= trade[cnt].fi;
}
else
{
sum += double(M)/trade[cnt].fi*trade[cnt].ji;
M = 0;
}
cnt++;
}
printf("%.3lf\n", sum);
}
return 0;
}