为防止广告,目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册(新用户需要等待1个小时才能正常使用该功能)。
USACO/milk
来自NOCOW
< USACO
[编辑] 分析
简单的贪心算法
将所有的牛奶按价格升序排列(用快排),然后从低到高买入,直到买够m为止。
贪心的证明:
假设某次买了价格稍高的牛奶,可以得到最优解。那么把这次买的牛奶换成价格更低的牛奶,其它不变,那么所得的解较优。假设不成立。
利用桶排的思想可以把代码压缩到极限!参见代码三!
因其价格范围为[0..1000]可以用计数排序来做,就可以得到一个傻瓜代码(参见代码四)。
最佳解题方法:
因为价格的范围在1..1000之内,所以,我们只要在读入数据的时候把相同价格的合并即可,进行计算时,也只需要for i:=0 to 1000 do进行扫描如果有价格为i的牛奶就收购即可,所以不需要排序。