贪心

概念

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 —–百度百科

概括的说 贪心算法就是通过某种策略 在进行每个决策时选择依据这种策略所得的最优解 从而发展为全局最优解

这与将所有可能的决策方案计算的动态规划算法不同

通常情况下 做贪心题的第一步是确认它是否有贪心解 许多动态规划题长的很想贪心如

P1880 [NOI1995] 石子合并

P1048 [NOIP2005 普及组] 采药

据说当年P1880有大量的人因误认为此题为贪心而做错 好耶！

在想出贪心策略后一定要思考 全局最优解能否从局部最优解转移得到

例题

T1 P1016 [NOIP1999 提高组] 旅行家的预算

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站ii离出发点的距离Di、每升汽油价格Pi（i=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入格式

第一行，D1，C，D2，P，N。

接下来有N行。

第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。

输出格式

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

显而易见

1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；

2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；

3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；

4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；

可以看出 全局花费最少一定是在当前可选油价最低加油站中加尽量合适的油的决策后转移来的 所以贪心正确

悬线法

（你也可以认为这是贪心与dp杂交的产物）（那晚 贪心和dp都长大了许多）

用于求解最大带限制矩形覆盖问题

定义

有效竖线：除两个端点外不覆盖任何障碍点的竖直线段

悬线：上端点到达边界或障碍点的有效竖线