Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2793296
  • 博文数量: 471
  • 博客积分: 7081
  • 博客等级: 少将
  • 技术积分: 5369
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-04 21:55
文章分类

全部博文(471)

文章存档

2014年(90)

2013年(69)

2012年(312)

分类: C/C++

2012-05-23 15:07:05

贪心算法HDU1009 FatMouse' Trade

题目大意:

老鼠有M磅猫食。有N个房间,每个房间前有一只猫,房间里有老鼠最喜欢的食品JavaBean,J[i]。若要引开猫,必须付出相应的猫食F[i]。当然这只老鼠没必要每次都付出所有的F[i]。若它付出F[i]a%,则得到J[i]a%。求老鼠能吃到的做多的JavaBean

解题思路:

老鼠要获得最多的食品,就要用最小的猫食换取最多的猫食,这就要求J[i]/F[i]的比例要大。J[i]/F[i]的比例越大,证明在这个房间,小鼠付出得到的收获最有价值。于是我们将设置结构体,结构体里设置percent放置J[i]/F[i]。然后对结构体数组进行排序。依次按比例排序的付出猫食,即可。

例子:

输入

5 3

7 2

4 3

5 2

J[i]/F[i]排序后:

7 2

5 2

4 3

在第一排数据上,小鼠付出2个猫食换得7JavaBean

在第二排数据上,小鼠付出2个猫食换得5JavaBean

在第三排数据上,小鼠只剩下1个猫食,便用这一个猫食换取1/3*4JavaBean

所以,总共换得13.333JavaBan



阅读(1694) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~