贪心

前置基础知识

满二叉树与完全二叉树

完全二叉树的特点：满二叉树去掉最下面一层，最右边的一些叶子。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

完全二叉树的一些重要性质：

• 1.具有 $n$ 个结点的完全二叉树的深度 $\left \lfloor \log n \right \rfloor +1$.

  如果深度为 $dep$ ,如果是满二叉树， $2^0+2^1+2^2+...+2^{dep-1}=2^{dep}-1$，由完全二叉树得到不等式 $2^{dep-1}-1>n,2^{dep}-1 \leq n$,得到 $dep=\left \lfloor \log n \right \rfloor +1$.

• 2.如果对一棵有 $n$ 个结点的完全二叉树的结点按层序编号, 则对任一结点 $p$ ($1 \leq p \leq n$), 父亲节点编号为 $\left \lfloor \frac{p}{2} \right \rfloor$,左儿子 $2p$ ,右儿子 $2p+1$

优先队列，STL基础知识请学习材料 - queue

例题 1.P1177 【模板】排序

• 手写堆，参考代码：点击

• 优先队列，参考代码：点击

例题 2.P1090 [NOIP2004 提高组] 合并果子

• 手写堆，参考代码： 点击

• 优先队列，参考代码：点击

  本题加强版，P6033合并果子 加强版 , 要求 $O(n)$ 解决。思路是，可以证明小的合并之后的堆是单调的，那么就可以用两个普通数组维护最小的两个堆，但是为了避免一开始排序，可以使用计数数组实现有序。从而实现时间复杂度 $O(n)$。

例题 3.P1168 中位数

• 对顶堆算法 参考代码：点击

• 当然本题还可以利用其他作法，比如树状数组+二分。

  类似题目：AtCoder - abc458_d

---

贪心常见模型

贪心是一种在每次决策时采取当前意义下最优策略的算法，因此，使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心是否正确，需要证明局部最优就是全局最优，考试中直接证明难度一般较大，常常使用反例否定掉某种“假贪心”。

注意:

1.有些问题局部最优，并不是全局最优。(鼠目寸光)典型的例子就是部分背包贪心正确，但01背包贪心是错误的。

2.选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

3.贪心经常采用微扰法（邻项交换）、范围缩放、决策包容性、反证法、数学归纳法 进行证明。

1.选择不相交区间

• 数轴上有 $n$ 个开区间 $(a_i,b_i)$，选择尽量多个区间，使得这些区间两两没有公共点。

贪心策略：按照$b_i$排序，$b_i$越早结束，后面能选择的越多。

例题4. P1803 凌乱的yyy / 线段覆盖

2.区间选点问题

• 数轴上有 $n$ 个闭区间 $[a_i,b_i]$ ，取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

贪心策略：按照 $b_i$ 排序，对于当前区间选取最右边的点，下一步直接跳到开始晚于 $b_i$ 的区间。

例题5. P1250种树

分析：按照区间右端点从小到大排序，选择种树的位置尽可能靠近右侧。对于每个区间，先统计区间内已经种了几颗树(使用标记数组)，剩下不够的树就是需要新种的数量，将其加入最终答案 ans 中，新这种的树再从后往前种，即标记数组。

参考代码：点击

例题6：P1325 雷达安装

分析：在岸边要装雷达覆盖小岛，雷达覆盖半径为 $d$,可以以小岛为圆心，半径为 $d$，圆与小岛的交点所对应的区间就是安装雷达的区间位置。那么问题就转成了，若干了闭区间，选择尽量少的点，使得每个区间都至少覆盖一个点。

参考代码：点击

3.区间覆盖问题

• 数轴上有 n 个闭区间 $[ai,bi]$ ,选择尽量少的区间覆盖一条指定线段 $[s,t]$。

例题7 U329674 喷水装置

分析：计算每个水龙头能覆盖草地的边界：

$l=x-\sqrt{d^2-(\frac{w}{2})^2},r=x+\sqrt{d^2-(\frac{w}{2})^2}$

按照左端点排序，符合覆盖位置的情况下(左端点小于要求覆盖位置)，选择右端点最大的区间,要求覆盖位置更新到选中区间右端点，循环直到达到$L$。

参考代码：点击

---

贪心其他例题选讲

例题8 P2887 [USACO07NOV] Sunscreen G

例题9 P1158 [NOIP2010 普及组] 导弹拦截

例题10 P1080 [NOIP2012 提高组] 国王游戏

例题11 P2827 [NOIP2016 提高组] 蚯蚓

例题12 UVA1316 Supermarket