贪心复习

题目

• [] 引水入城 思维比较巧妙，通过记忆化搜索把问题转化为线段覆盖问题(最小先端覆盖就贪心地找l端点小于当前pos，右端点最长的地方的线段)
• [] woj2380分配防晒霜 把奶牛按照最小限制从大到小排序，然后找一个满足条件的最大的来满足，因为对于x和y 若spf[x]<spf[y] 那么对于后面的奶牛只会出现xy都能用 xy都不能用 x能用 y不能用(不存在x不能用y能用，因为是按照最小限制排序的)所以选择spf较大的y不会使解变得更劣
• [] stall reservations 就是贪心地找结束时间最早的牛栏，如果不满足，则新增。堆优化。
• [] poj2054神仙贪心 较难，要推式子，改天再来补
• [] poj1328 把每个点的合法雷达做成一条线段，然后就是选最少的点使得每个点选都有点
• [] poj1050 水
• [] hdu4864 给出n个机器和m个任务，对于一天来说，每个机器有最大工作时间xi,可接受最大等级yi,每个任务有一个工作时间xi，一个等级yi，可获价值为500xi+2yi，任务需要在一台机器一天内完成，问我们一天可得到的最大价值。因为y对结果的影响非常小，就直接选择所要x满足的机器里面，选择一个y最小的机器就好了，代码比较巧妙，用了个桶。这道题需要注意到y的范围非常小，小于100，所以优先满足x是最优策略。

今天写的比较匆忙，一定要总结好，理解好啊啊啊啊没时间了