贪心算法大楼

admin

贪心算法，就是按照一定的准则去选择最优解。一般来说，这个标准是统一的，全局通用。表现在程序里面就是就是数据排个序，或者找最大值。


典型例题：

1、P1223 排队接水 http://hsyit.cn/forum.php?mod=viewthread&tid=35902 排序后由小到大
2、P1781 宇宙总统 http://hsyit.cn/forum.php?mod=viewthread&tid=36232  有点意思，字符串按照数值比较大小
3、P1208 [USACO1.3]混合牛奶 Mixing Milk   http://hsyit.cn/forum.php?mod=viewthread&tid=36339  排序后从最便宜的开始买起
4、P1094 纪念品分组  http://hsyit.cn/forum.php?mod=viewthread&tid=36228 排序后看看最大的和最小的能否配对，可以的话配对，否则单独选择最大的。
5、P3955 图书管理员  http://hsyit.cn/forum.php?mod=viewthread&tid=36307  书号由小达到排序 符合条件的第一个就是最小的


以上的贪心准备都比较好找，题目实现也都很简单。

admin

贪心的准则要找到不容易，简单的还好说，下面的就不是那么容易了，一般可能涉及2-3个因素。
P1803 凌乱的yyy / 线段覆盖 http://hsyit.cn/forum.php?mod=viewthread&tid=36340  按右端点排序，合并
P1106 删数问题  http://hsyit.cn/forum.php?mod=viewthread&tid=36294
P1012 拼数 http://hsyit.cn/forum.php?mod=viewthread&tid=35806
P1095 守望者的逃离  http://hsyit.cn/forum.php?mod=viewthread&tid=36003
P1080 国王游戏 http://hsyit.cn/forum.php?mod=viewthread&tid=35831
手电过河 http://hsyit.cn/forum.php?mod=viewthread&tid=36322

P1016 旅行家的预算 http://hsyit.cn/forum.php?mod=viewthread&tid=35853  便宜的话尽量加，贵的话加到刚好能到下一个油站
P1056 排座椅  http://hsyit.cn/forum.php?mod=viewthread&tid=35824
P1090 合并果子  http://hsyit.cn/forum.php?mod=viewthread&tid=36224  每次选择最小的两堆合并成一大堆然后加入统计。