贪心讲解(I)

## 简介 贪心，就是在对问题求解时，总是采用当前最好的选择。但是贪心算法不一定正确，一是问题不适用贪心，二是贪心思路不正确。在赛场上，一般没时间证明~~除非神仙~~，只需试试能不能举出反例(说不定可以拿来骗分)。贪心有难有易，同时有可能结合别的算法一起呈现，比如二分判定答案可能就会用到贪心。 接下来，我会结合几道例题，提炼出一些比较有用的贪心思路 ## 某些技qio 1. 通过样例推结论 某些题通过样例及其说明可以猜到正解。但是有些毒瘤题样例会使错误贪心表面上正确，还需多多证明 2. ~~多刷题~~ ## 动态规划? 动态规划和贪心正确性都基于问题的最优子结构性。但是有部分问题贪心不能用而动态规划能用(走方格)，也有部分问题动态规划明显没有贪心简单。 ## 例题 ### 旅行家的预算 #### 题面 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离$D1$、汽车油箱的容量$C$（以升为单位）、每升汽油能行驶的距离$D2$、出发点每升汽油价格$P$和沿途油站数$N$（$N$可以为零），油站$i$离出发点的距离$D_i$、每升汽油价格$P_i(i=1,2,…,N)$。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。 #### 思路 先骗个分，判无解。无解的情况就是开到一半没油了。枚举每个加油站，如果加满油还是开不到下一个加油站就是无解，无解可以在下文的正解思路中一起判。 开始考虑正解。这一次旅行，最关键的就是每个加油站和终点，所以我们从起点加油站开始模拟，直到终点。 我们梳理一下思路 - 路程固定 - 单位路程内耗油量固定 这两个有什么用呢？从这两条信息可以推导出，最优解必须满足加的油最好刚好用完，因为开完路程的耗油量是固定的，所以加的油如果没用完就会浪费。我们得到 - 要加的油固定 现在就更方便了，要想让花费最少，就要尽量加便宜的油。我们用贪心思想，推导出接下来的模拟需要满足以下两个条件 - 油不能浪费 - 尽量加便宜的油 我们挑选任意一个加油站，开始模拟(这是在讲思路，真正做题不是这样做的)。可以分两类讨论： - 在加满油可以开到的范围内中有油价比当前加油站便宜的车站 - 在加满油可以开到的范围内中没有油价比当前加油站便宜的车站 第一类比较容易，肯定是先使油能够开到离自己最近且比当前加油站便宜的油站，我们设红色是当前加油站加的油，橙色是离自己最近且比当前加油站便宜的加油站加的油，见下图：  很明显，橙色段比红色段便宜，所以上面的比下面的便宜，那么正确性便体现出来了。接着我们做完一系列的更新，就把当前位置调整至那个加油站 第二类稍麻烦。如果可以直接开到终点，那就直接开，否则类似上面那张图，会亏。如果不能直接开到终点，我们就加满。首先因为不能直接开到终点，所以这不会造成任何浪费。还是上图，橙色表示当前加油站的油，红色表示当前加油站所能开到的其它加油站的油，如下：  橙色段比红色段便宜，所以按下面的方法开省钱。加满之后，开到范围内最便宜的车站，再作下一步决定。 至此，我们发现，这个问题的解题思路已经被我们解决了 #### 小结 1. 不浪费或是浪费尽量少，这对于很多问题都有效果 2. 画图分析，这在像思路时会给予帮助 3. 分类讨论，找到解决方案 4. 这类可以归结为贪心+模拟的问题 --- ### 国王游戏 #### 题面 设有一个二元组$(l_i,r_i)$的排列，除排列的第一个元素$(l_0,r_0)$外，其它二元组的权值等于它前面的二元组$l$的积除以该二元组的元素$r$。试对除了第一个二元组外其它二元组进行排列，使权值最大的二元组权值最小。 #### 思路 这道题要用到高精度，这里不讨论。 我们从比较小的情况分析  排列情况如上 易得$ans_{1}=max(\frac{l_{0}*l_{1}}{r_{2}},\frac{l_{0}}{r_{1}})$ 另一种排列如下  易得$ans_{2}=max(\frac{l_{0}*l_{2}}{r_{1}},\frac{l_{0}}{r_{2}})$ 比较明显的关系有：$\frac{l_{0}*l_{1}}{r_{2}}>\frac{l_{0}}{r_{2}},\frac{l_{0}*l_{2}}{r_{1}}>\frac{l_{0}}{r_{1}}$ 若要$ans_{1}<ans_{2}$，则有$\frac{l_{0}*l_{1}}{r_{2}}<\frac{l_{0}*l_{2}}{r_{1}}$，化简得$l_{1}*r_{1}<l_{2}*r_{2}$ 所以$l_{1}*r_{1}<l_{2}*r_{2}$是$ans_{1}<ans_{2}$的充要条件 所以$l_{1}*r_{1}<l_{2}*r_{2}$越小放越前面 #### 小结 1. 对于一系列数学式子，可以通过构造不等式来得到贪心方法 2. 举较小规模的例子模拟 3. 这类可以归结为贪心+有数论意味的题 #### 练习 [[HAOI]糖果传递](https://www.luogu.org/problemnew/show/P2512) 即推出答案表达式贪心求得最优解 --- ### 喷水装置 #### 题面 ~~这道题好像洛谷上没有??~~ 长$L$米，宽$W$米的草坪里装有$n$个浇灌喷头，每个草坪都装在草坪的中心线上(离两边各$\frac{W}{2}$米)。我们知道每个喷头离草坪中心线左端的距离，以及它的浇灌范围(是一个正圆，给出半径)，问最少几个喷头能够同时浇灌整块草坪。 #### 思路 为方便后文讲解，现设第$i$个喷水装置位置(上文所谓距离)为$a_{i}$，浇灌半径为$r_{i}$。 乍一看，这道题像是覆盖一个区间，但是它是用圆覆盖长方形，这让人有点犯难。 但是，我们看下图：  (为方便只绘制了几个) 这个图形是一个以长方形两宽中点连线段所在的直线为对称轴的轴对称图形(这表述对得起我敬爱的语文数学老师)。所以我们可以只看上部分。再接着看，我们称一个圆真正浇灌范围是一个不需要其它圆再覆盖的部分。  再接着看，我们称一个圆真正浇灌范围是一个不需要其它圆再覆盖的部分。如上图，黑色部分是圆没有覆盖到的地方，但是这周围两个圆明明最左/最右端点已经超过了啊，可是圆就是这样，所以这一块(包括它们正下方圆有覆盖的地方)不属于圆的真正浇灌范围。那么一个圆的真正浇灌范围是哪里呢?  如上图最右边的圆，它的真正浇灌范围用黑色块表示，容易发现，这是个长方形，而且长方形的两个端点正是圆与草坪上方的两个交点。上图中有两个圆，并没有与草坪上方有两个交点，也就是说这些圆真正浇灌范围为0，下面的讨论中不考虑这一类圆，它们的共同特征是$r_{i}\le\frac{W}{2}$。 接下来就不放图了，因为如果你把圆换成长方形，就会发现它等价于有$n$个线段覆盖一个区间。对于这类区间覆盖问题，属于贪心中很经典的一类。在说区间覆盖问题的思路前，还有一个问题，一个圆所对应的线段两端点坐标应该怎么求呢?连接该圆心与该圆和草坪上方的两个交点，再取圆心到草坪上方的垂线段，运用勾股定理(这个不需要展开讲了吧，不懂自行百度)即可求出。这边给出计算代码： ```cpp seg[i].l=a[i]-sqrt(r[i]*r[i]-(W/2)*(W/2)); seg[i].r=a[i]+sqrt(r[i]*r[i]-(W/2)*(W/2)); ``` 自行理解吧 区间覆盖问题怎么求呢?区间覆盖的形式化描述是这样的：给定$n$个闭区间$[a_{i},b_{i}]$，选择尽量少的区间覆盖一条指定的线段(闭区间)$[s,t]$。 做法是将区间以左端点坐标为关键字从小到大排序。一开始选点$s$，找到能覆盖点$s$的区间中右端点坐标最大的区间$[a_{i},b_{i}]$，并取点$b_{i}$继续执行上面的操作，直到当前取的点坐标大于$t$为止。 #### 小结 1. 这类问题可以归结于区间覆盖问题，区间覆盖问题的思路上面已经扯到了 2. 要善于转化问题为基本算法模型(这在图论中也是很重要的) 3. 过滤掉一些无用的东西，在上文中的体现是去掉圆的一部分 --- ### 钓鱼 #### 题面 小明有$H(1\le H\le 16)$个小时钓鱼，假设有$N(2\le n\le 25)$个鱼塘都在一条水平路边，从左边到右编号为$1,2,3...n$，小明希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。他测出从第I个湖到$i+1$个湖需要走$5*t_i$分钟的路，还测出在第I个湖边停留，第一个5分钟可以钓到鱼$f_i$，以后再每钓$5$分钟鱼，鱼量减少$d_i$。为了简化问题，他假定没有其他人钓鱼，也不会有其他因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的数量。 #### 思路 题目条件限制太多，我们先考虑钓鱼怎么钓。显然，每次求能钓到最多的鱼塘钓即可，具体写个堆。但是我们添加了走路的过程，就头痛了。 这次我们只考虑走的过程，即走的路最少。只要不走回头路不就OK了？ 结合起来:从头走到尾，选最多的钓。但是我们很快反应过来:假设第一次钓最多的鱼塘在后面，但是第二次钓最多的鱼塘在前面，这不就违反上面的思路了吗？别慌，在鱼塘里钓鱼并不会影响其它鱼塘的鱼——也就是说钓鱼的次序调换并不会影响最后掉到的鱼的总量。我们在每次选择最大值时仍按原方案，但是计算总路程时重新给次序排成最优方案即可，在这里我们认为最短距离就是总路程。 那么总路程是多少呢？是从头到尾吗？如果限定时间内走不到怎么办呢？是从头到能走到的最远的鱼塘吗？如果最优方案并没有到那个鱼塘怎么办呢？既然不能明确总路程，那么我们就枚举每个鱼塘，对每一次枚举求局部最优解，最后选最优解即可，当然，只需枚举到最远能在限定时间内到达的鱼塘即可。 还有一个小技巧，可以把五秒作为一个时间单位来计算。 #### 小结 1. 这类问题可以归结于动态求最值的问题，可以用堆解决问题 2. 对于某些不确定的值，采用枚举求最优解的方法(以前看到过一道差分约束题因为变量在不等式右边，所以把变量视作定量枚举求最优) 3. 题目限制条件多的，可以拆分来看 #### 练习 [合并果子](https://www.luogu.org/problemnew/show/P1090) 特别简单的一道题 ## 总结 贪心是一种思想，而非算法，所以很难抽象地去讲解，只能通过这种结合例题的方法去讲解。由于贪心不一定正确，在想出一种思路后最好找找反例或者自己证明。贪心在图论中也有自己的用武之地(Prim,Dijstra,Kruskal)