专题 18 贪心 · 复习强化

考点：贪心的定义（A1）。

（A1）考点：贪心的定义——每步取当前局部最优且绝不反悔。

解析：本题考查贪心的定义。贪心把求解过程看成一系列不可撤销的选择：每个决策点只依据当前信息选局部最优，选完就走、不回头、不比较其他分支。快是快，但正确性完全取决于问题是否配合（A3）。

排除法：D 选全部列出再选的人描述的是枚举；B 选分成两半再合并的人描述的是分治；C 选随机多试的人描述的是随机化算法，都没有「不反悔的局部最优」这层。

考点：贪心不是万能的（A2）。

（A2）考点：贪心不是万能的——只在满足贪心选择性质的问题上保证最优。

解析：本题考查贪心不是万能的。贪心的答案由一系列局部选择拼成，若存在「先吃小亏后占大便宜」的结构（如 01 背包），局部最优会堵死全局最优。用前先问一句「这个策略有没有反例」（A6、E5）。

排除法：C 选对所有问题都最优的人高估了它的威力；B 选永远比 DP 差的人走了另一个极端——活动安排等题贪心既快又对；D 选只能用于排序的人把预处理当成了全部疆域。

考点：贪心选择性质（A3）。

（A3）考点：贪心选择性质——全局最优可由一系列局部最优选择构造。

解析：本题考查贪心选择性质。它是贪心正确性的数学核心：存在某个全局最优解，它的第一步恰是贪心的选择；去掉这一步，剩下的仍是同类子问题的最优解。两句话合起来保证「一路贪心到底」就是最优。

排除法：A 选每步全局最优的人把目标当成了手段——局部选择只看局部；D 选数据必须有序的人把常见预处理当成了性质本身；C 选只能进行一次的人没理解「一系列选择」。

考点：贪心与最优子结构（A4）。

（A4）考点：贪心与最优子结构——最优解包含子问题的最优解。

解析：本题考查贪心与最优子结构。这是贪心与 DP 共用的前提：大问题的最优解里嵌着子问题的最优解。区别在贪心额外要求贪心选择性质，DP 只要求无后效性——所以 DP 的适用面更宽。

排除法：C 选子问题互不相交的人描述的是分治特征；D 选子问题个数是常数的人加了一条不存在的要求；A 选必须小一半的人把分治的分割方式错安过来。

考点：贪心与枚举动态规划（A5）。

（A5）考点：贪心与枚举动态规划——贪心每步一个选择，快但需论证。

解析：本题考查贪心与枚举动态规划。枚举展开所有决策组合（指数级）、DP 记录每个子问题的最优（多项式但要填全表）、贪心每步只押一个选择（通常一趟排序加一趟扫描）。三者是「正确性与速度」的不同交易点。

排除法：C 选枚举所有组合的人描述的是枚举；B 选永远比 DP 慢的人把最快说成了最慢；D 选必须递归树的人把实现形式当成了定义。

考点：反例验证贪心（A6）。

（A6）考点：反例验证贪心——一个具体反例即可否定策略。

解析：本题考查反例验证贪心。要证明贪心不对，不需要长篇论证：找一组数据，按贪心走出的解严格劣于一个可行解，策略即被否定（F5、P3 都是现成反例）。反过来，验证一万组数据全对也只是增强信心，不构成证明。

排除法：C 选一般都不对的人是在下空泛断言，不如一个具体反例有力；B 选别的题错过的人犯了「迁移罪」——每道题的策略要单独检验；A 选看代码行数的人把工程量当成了正确性。

考点：贪心的整体框架（A7）。

（A7）考点：贪心的整体框架——定策略（常含排序）、逐步选择、得答案、验证。

解析：本题考查贪心的整体框架。四步里最重的是第一步：确定「按什么顺序、选什么」——排序键就是策略的化身（C6）。选完后线性扫描一遍出答案；不稳的策略配对拍验证（D5）。

排除法：A 选递归记忆化的人描述的是 DP 流程；B 选建图遍历的人描述的是图论流程；D 选状态转移初始化的人还是 DP 的四步。

考点：找零钱的贪心（B1）。

（B1）考点：找零钱的贪心——优先大面额，人民币面额体系下 87 元 6 张。

解析：本题考查找零钱的贪心。$87=50+20+10+5+1+1$ 共 $6$ 张，每步用不超余额的最大面额。该策略对人民币成立依赖面额间的整倍嵌套关系（H3）；对 $\{1,3,4\}$ 这类体系会翻车（F5）。

排除法：D 答 $5$ 张的人某一步面额选小了多拼了张数；C 答 $7$ 张的人多用了小面额；A 答 $87$ 张的人全用一元，没走大面额优先。

考点：活动安排的策略（B2）。

（B2）考点：活动安排的策略——按结束时间排序，选最早结束且不冲突者。

解析：本题考查活动安排的策略。结束越早、给后续留的空当越大；排序后线性扫描，能选就选。这是「区间调度」的标准解，真题级高频（J1 数据实测 $3$ 场）。

排除法：C 选按开始时间的人会被早开始晚结束的长活动坑（P2）；A 选按时长的人对「短但错位」的组合无保证；B 选随机的人放弃了策略。

考点：排队接水的顺序（B3）。

（B3）考点：排队接水的顺序——短者先接，总等待最小。

解析：本题考查排队接水的顺序。第 $i$ 个人的接水时间会被他后面的每个人等一遍：让耗时短的先进场，被「复制」的等待最少。交换论证可证任何「前长后短」的相邻逆序交换都不变差（F3）。K2 实测 $\{3,1,2\}$ 等待和 $4$。

排除法：A 选长者先排的人把等待放大；D 选按到达顺序的人放弃了优化；B 选总和都一样的人没算过换序的差别。

考点：部分背包的策略（B4）。

（B4）考点：部分背包的策略——按单位价值降序装，装不完的割最后一件。

解析：本题考查部分背包的策略。物品可分割时，「每一克容量都要装单位价值最高的」显然不亏，贪心可证最优。K1 实测 $\{2,3,4\}$、$C{=}6$ 得 $8.5$。注意与 01 背包的分界：不可分割时贪心失效（E5）。

排除法：B 选按总价值的人被大而重低效的物品占满容量；A 选按重量从轻的人忽略了价值密度；C 选随便装的人放弃了策略。

考点：合并果子的策略（B5）。

（B5）考点：合并果子的策略——每次合并最小两堆，小根堆维护。

解析：本题考查合并果子的策略。每合并一次，合成的新堆若还要再合并，其「体积」会被再次计入——越早合并的小堆被计费的次数越多，所以要让小的先进场被反复合并、大的尽量晚合并。哈夫曼思想（H4），L1 实测 $\{1,2,9\}$ 代价 $15$。

排除法：A 选每次最大两堆的人方向全反，大堆反复计费代价暴涨；D 选按输入顺序的人完全没用策略；B 选先合并中间大小的人没有依据。

考点：均分纸牌的传递（B6）。

（B6）考点：均分纸牌的传递——逐堆结算差值向右传递，欠账非零即一次移动。

解析：本题考查均分纸牌的传递。从左到右累计「与均值的差」：差为零说明前段自洽不必动；非零则必须与右邻交换一次。M5 实测 $\{9,8,17,6\}$（均值 $10$）得 $3$ 次。贪心视角：欠账只在相邻间结清，绝不绕道。

排除法：A 选最多给最少的人是朴素模拟，会多走弯路；C 选先排序的人破坏了「相邻传递」的结构限制；B 选无法贪心的人低估了逐堆结算的威力。

考点：删数问题的策略（B7）。

（B7）考点：删数问题的策略——删第一个比后一位大的数字（削峰）。

解析：本题考查删数问题的策略。高位越小数越小：扫到第一个「下降沿」（前大于后）删掉大的那个，等于把高位压小；全程递增则删末位。K5 实测 $15763$ 删 $2$ 个得 $153$，M6 实测 $1432219$ 删 $2$ 个得 $12219$。

排除法：B 选删最大数字的人忽略了位置——低位的 $9$ 不如高位的 $7$ 碍事；D 选删前 $k$ 个的人丢掉了高位小的机会；C 选删最小数字的人把小数字删掉了方向全反。

考点：拼接最小数的策略（B8）。

（B8）考点：拼接最小数的策略——按拼接字典序 x+y 与 y+x 比较。

解析：本题考查拼接最小数的策略。两个串谁放前面，看两种拼法谁小；这条比较规则有传递性，可直接排序。M1 实测 $\{32,3,321\}$ 最小拼 $321323$、最大拼 $332321$。若按数值排，$3$ 排最前会得到错误的 $32321$ 开头。

排除法：B 选按数值从小到大的人没注意 $32$ 与 $3$ 的相对序取决于拼接而非数值；D 选按位数的人忽略了内容；C 选按首位从大到小的人方向反了且忽略次位。

考点：区间调度按右端点（C1）。

（C1）考点：区间调度按右端点——结束早给后面留得多，每步安全。

解析：本题考查区间调度按右端点。直观理解：固定选了某个区间，它「占用」的截至时刻是右端点；右端点越早，后续可选空间越大。交换论证可把任何最优解调整成「首区间换成结束最早的」不变差（F3 同思路）。

排除法：A 选右端点小则长度短的人把两个概念划等号——短可能开始得晚；D 选不需要再判断重叠的人忘了排序后仍要比较开始与上一选中右端；C 选左端点排序同样正确的人被 P2 的数据打脸。

考点：区间选点（C2）。

（C2）考点：区间选点——按右端点排序，缺点则放右端点。

解析：本题考查区间选点。点放在当前区间右端点，能覆盖右侧尽可能多的后续区间（它们右端更靠右、左端却可能很近）。J2/O3 实测 $\{\{1,4\},\{2,3\},\{3,5\},\{6,8\},\{5,7\}\}$ 放点 $3$ 与 $7$ 共 $2$ 个。

排除法：B 选放中点的人对「区间长短悬殊」的情形浪费；C 选放左端点的人只照顾左侧区间，后续覆盖差；D 选每区间单独放的人放弃了共享机会。

考点：区间覆盖（C3）。

（C3）考点：区间覆盖——按左端点排序，每步在可衔接线段中选右端最远者。

解析：本题考查区间覆盖。已覆盖到位置 $p$ 时，只有左端 $\le p$ 的线段能接上；在这些线段里把右端推得最远，步数才最少。J3 实测六条线段盖 $[0,10]$ 用 $3$ 条（$(0,3),(3,8),(6,10)$）。2020 年完善真题正是这一模型。

排除法：A 选每次最长的人可能接不上（左端在覆盖之外）；D 选左端最小不再比较的人遇到「左端相同右端不同」就错；B 选随机的人放弃了策略。

考点：最少教室数（C4）。

（C4）考点：最少教室数——按开始排序配小根堆，复用最早空闲教室。

解析：本题考查最少教室数。按开始时间逐个处理活动，小根堆里存各教室的空闲时刻；新活动的开始时刻不早于堆顶（最早空闲）就可复用那间，否则新开一间。J4 实测五场活动 $2$ 间教室。它等价于求「任意时刻的最大同时进行数」（C5）。

排除法：A 选等于活动总数的人是最坏情形（全重叠）的过估；D 选按时长分配的人没有复用逻辑；B 选每活动新开一间的人把最坏当常态。

考点：区间分组（C5）。

（C5）考点：区间分组——最少组数等于最大同时进行数。

解析：本题考查区间分组。把重叠活动分进不同组，任一时刻同时在进行的活动各占一组，所以组数下界是「最大同时数」；按 C4 的贪心恰能达到这个下界。换角度理解同一问题，是区间贪心的常见思维训练。

排除法：B 选活动总数一半的人把统计结论当成了随口公式；C 选最长活动时长的人量纲都不同；A 选端点种数的人把数据特征当成了答案。

考点：排序是贪心的预处理（C6）。

（C6）考点：排序是贪心的预处理——把「处理顺序」变成确定的键序。

解析：本题考查排序是贪心的预处理。贪心要「每步知道选谁」，排序把候选按关键量排好，扫描时第一个满足条件者即所求。排序键就是策略：接水按耗时、调度按结束、拼数按拼接序（D3）。

排除法：A 选排序本身出答案的人忘了排序后还有选择与判断；B 选保证永远正确的人高估了排序——键错了照样翻车（P2）；D 选题目要求的人把手段误解成了任务。

考点：区间贪心的套路（C7）。

（C7）考点：区间贪心的套路——选点类按右端、覆盖类按左端，配一个扫描变量。

解析：本题考查区间贪心的套路。记忆法：要「早点结束腾地方」的按右端点排（调度、选点）；要「早点开始往前铺」的按左端点排（覆盖）。扫描时维护一个变量（最后选中右端 / 已覆盖末端），一趟过完。J 组全部代码都是这两板斧的变体。

排除法：C 选两两比较的人回到 $O(n^2)$ 且没抓住贪心结构；B 选枚举子集的人放弃了贪心；A 选按编号处理的人让策略缺席。

考点：先排序再贪心（D1）。

（D1）考点：先排序再贪心——接水按耗时升序排序即最优安排。

解析：本题考查先排序再贪心。接水问题排序后依次接水，答案直接出来——排序就是贪心策略的执行。二分也需要有序，但排序在那里是「满足前提」，与贪心里「排序即策略」不同。

排除法：C 选二分查找的人混淆了「排序作为前提」与「排序作为策略」；A 选前缀和的人排序毫无必要；D 选 DFS 的人把遍历与贪心混为一谈。

考点：最值贪心（D2）。

（D2）考点：最值贪心——每步直接取当前最大或最小。

解析：本题考查最值贪心。最朴素也最常用的贪心形态：每次选剩余中的最值元素（I3 的两次最大、合并果子的最小两堆）。它成立与否取决于「最值被取走后不破坏后续的最优结构」，用反例或证明把关。

排除法：C 选求全局最大最小的人把「每步取最值」错记成「只算两个最值」；D 选二分的人用了另一算法；B 选只处理最大最小的人丢掉了逐步推进的循环结构。

考点：从限制条件找排序键（D3）。

（D3）考点：从限制条件找排序键——限制所在即键所在。

解析：本题考查从限制条件找排序键。接水的限制是「后面的人陪等」——耗时是键；调度的限制是「占用时段」——结束时刻是键；拼数的限制是「相邻拼接」——拼接序是键。从「谁碍事、怎样少碍事」出发，键自然浮出。

排除法：C 选永远用数值本身的人做不对拼数这类比较型问题；B 选随机选键的人把设计交给了运气；A 选键越多越好的人没理解键是唯一的策略核心。

考点：交换论证（D4）。

（D4）考点：交换论证——最优解可逐步调整为贪心解且不变差。

解析：本题考查交换论证。证明套路：任取最优解，找到与贪心不同的一处，交换成贪心的选择，证目标值不降（或不升）；反复交换后最优解变成贪心解——贪心同样最优。它是最常用的贪心证明工具（F3 落地）。

排除法：D 选交换输入输出的人完全跑题；B 选把递归改循环的人说的是迭代化；A 选交换升降序的人只想到排序参数。

考点：对拍验证贪心（D5）。

（D5）考点：对拍验证贪心——小数据随机对拍暴力，一致增信心。

解析：本题考查对拍验证贪心。写一个朴素枚举/搜索的正确版本，与贪心在小随机数据上批量对拍：全对说明暂未找到反例，错一对即拿到反例。它给的是工程信心不是数学证明（A6 的分寸）。竞赛实战必备技能。

排除法：D 选肉眼样例的人样本量太少抓不到边角反例；C 选提交看分的人把验证成本转嫁给了评测机；A 选不需要验证的人把贪心的软肋当成了免检金牌。

考点：贪心的复杂度（D6）。

（D6）考点：贪心的复杂度——排序主导的 O(n log n)。

解析：本题考查贪心的复杂度。先排序后线性扫描的贪心，复杂度 $O(n\log_2 n)+O(n)=O(n\log_2 n)$；不排序的简单贪心（找零、跳跃）是 $O(n)$ 或 $O(\text{面额数})$。快，是贪心在适用题上的最大红利。

排除法：C 答 $O(n)$ 的人忽略了排序代价；B 答 $O(n^2)$ 的人多算了一层不存在的循环；A 答 $O(2^n)$ 的人把它与枚举混同。

考点：贪心失效的信号（D7）。

（D7）考点：贪心失效的信号——决策牵制不可分割时优先想 DP。

解析：本题考查贪心失效的信号。物品不可分割、选择之间「占资源互相挤兑」（01 背包型结构）、或局部最优明显堵死后续组合，都是贪心红灯；此时 DP 把每个子问题的所有决策都算一遍才有保证。E5 的 $7$ 对 $8$ 就是信号兑现。

排除法：B 选数据有序的人恰好是贪心友好信号；C 选求最小值的人把目标类型当成了结构信号；A 选数据范围 $1000$ 的人把规模当成了结构——范围只影响算法量级选择（E6）。

考点：贪心与动态规划（E1）。

（E1）考点：贪心与动态规划——DP 全决策保证最优，贪心单决策需性质背书。

解析：本题考查贪心与动态规划。DP 对每个状态比较所有转移取最优，正确性「自带」；贪心每状态只走一条路，快但要求问题满足贪心选择性质。能贪心的题 DP 都能做（可能更慢），反之不然——01 背包只能 DP。

排除法：D 选只能递归的人忘了迭代填表；A 选不能与排序配合的人没见过接水、调度；B 选毫无联系的人忽略了共享的最优子结构前提。

考点：贪心与枚举（E2）。

（E2）考点：贪心与枚举——枚举展开全部决策树，贪心每层只留一枝。

解析：本题考查贪心与枚举。枚举在每个决策点分出所有分支再逐一评估（指数级）；贪心在同一棵决策树上每层只保留一个分支直奔叶子。速度差是指数级的，代价是贪心可能错过被剪掉的更优叶子。

排除法：B 选完全相同的人没看到剪枝差异；A 选枚举更快的人违背量级常识；C 选并行版本的人凭空发挥。

考点：贪心与分治（E3）。

（E3）考点：贪心与分治——分治切独立子问题再合并，贪心逐步选择不切分。

解析：本题考查贪心与分治。分治把问题剖成几个同型子问题分别击破再拼答案；贪心不剖分问题，而是在时间维度上一步步做选择。归并排序是分治不是贪心，虽然两者都常与排序沾边。

排除法：B 选都每步选最优的人把分治的「切」误记成了「选」；A 选分治必须排序的人把个别例子当定义；C 选贪心必须递归的人把实现当本质。

考点：贪心与回溯（E4）。

（E4）考点：贪心与回溯——贪心不反悔，回溯撤销重试。

解析：本题考查贪心与回溯。回溯在选择点「试探—撤销—换路」，把决策树走遍；贪心选了就锁死。回溯全面但慢（指数级），贪心快但可能错。工程上常用「贪心剪枝 + 回溯兜底」的组合。

排除法：A 选回溯不能求最优的人没见过全排列取最优的暴力解；D 选必须配合使用的人把它们当成了强制捆绑；C 选没有区别的人忽略了反悔机制这层根本差异。

考点：零一背包的反例（E5）。

（E5）考点：零一背包的反例——贪心 7 对 DP 8。

解析：本题考查零一背包的反例。$\{2,3,4\}$、$\{3,4,5\}$、$C{=}6$：贪心按单位价值先装 $w{=}2$（$1.5$）再装 $w{=}3$（$1.33$）得 $7$、剩容量 $1$；最优组合是 $w{=}2{+}4$（恰 $6$）价值 $8$。高密度小件挤掉了更优的「中密度组合」。一个数据，判了「单位价值贪心」在 01 背包上的死刑。

排除法：C 答 $7$ 为最优的人没找到 $2{+}4$ 的组合；B 答 $9$ 的人把三件全装（重 $9$ 超容）；D 答 $12$ 的人价值全加没看容量。

考点：数据范围暗示贪心（E6）。

（E6）考点：数据范围暗示贪心——$10^6$ 以上线性/对数算法，DP 表开不下。

解析：本题考查数据范围暗示贪心。$n\le10^6$ 甚至 $10^9$ 时，$O(n^2)$ 的 DP 表内存与时间都爆炸，可行解只剩排序扫描（贪心）、双指针或数学式。反过来 $n\le1000$ 常暗示 $O(n^2)$ DP。范围是算法选型的第一道筛子。

排除法：D 选 $O(n^2)$ DP 的人在 $10^6$ 上会超时超内存双重暴毙；A 选指数枚举的人量级差得更远；C 选无关的人低估了出题人用范围传达的信号。

考点：贪心证明的结构（F1）。

（F1）考点：贪心证明的结构——贪心选择安全 + 剩余是最优子问题，双归纳。

解析：本题考查贪心证明的结构。两步走：证存在最优解以贪心首步开头；证其后剩余问题独立成同类子问题。两步成立则归纳可得每一步贪心都安全，整条贪心链最优。这个骨架覆盖了绝大多数教材证明。

排除法：B 选随机数据全对的人把实验当证明；A 选通过编译的人把语法当数学；C 选样例正确的人样本量近乎零。

考点：反证法证明（F2）。

（F2）考点：反证法证明——假设最优解都不含贪心选择，换入后不变差即矛盾。

解析：本题考查反证法证明。标准句式：设所有最优解的第一步都不同于贪心；取其一，把它第一步换成贪心的选择，证（常用交换论证）价值不变差——于是存在含贪心首步的最优解，与假设矛盾。矛盾即证明。

排除法：C 选重写一个贪心的人不是证明；D 选换数据的人改的是输入不是论证；A 选改答案的人把待证结论当成了可编辑对象。

考点：交换论证证明（F3）。

（F3）考点：交换论证证明——相邻逆序交换不变差，逐步调整到贪心序。

解析：本题考查交换论证证明。接水题：任取最优序，若存在前长后短的相邻对，交换后两人的完成时刻互换，后队等待减少量 $\ge0$，总等待不增；反复消去逆序即得短者在前且仍最优。邻交换可推广到全序，是排序类贪心的万能钥匙。

排除法：D 选看时间和是否相等的人没比较交换前后；C 选删数据的人破坏了问题；B 选交换输入输出的人跑题。

考点：归纳法证明（F4）。

（F4）考点：归纳法证明——首步奠基、步步归纳贪心安全。

解析：本题考查归纳法证明。奠基即贪心选择性质的第一半；归纳假设「前 $k$ 步贪心可扩展为最优解」，把第 $k{+}1$ 步看成剩余子问题的第一步再用奠基，归纳完成。与 F1 的骨架是同一件事的两面。

排除法：A 对数组长度从 $1$ 到 $n$ 逐个跑程序的人做的是测试不是证明；C 选证明排序正确的人只证了预处理；B 选证递归深度的人跑题到复杂度（选项中的 $1$ 到 $n$ 是跑程序的循环，不是归纳的步进）。

考点：反例否定贪心（F5）。

（F5）考点：反例否定贪心——{1,3,4} 找 6 元：贪心 3 张、最优 2 张。

解析：本题考查反例否定贪心。贪心 $4+1+1$ 三张，最优 $3+3$ 两张——「优先大面额」在非整倍面额体系当场翻车。它同时解释了 B1 的人民币为何能用贪心：面额层层整倍嵌套（H3）。一个反例胜过千言论证。

排除法：A 选贪心两张的人没实际模拟 $4{+}1{+}1$ 的过程；C 选两者都两张的人高估了贪心；D 选都三张的人低估了最优。

考点：过河问题（G1）。

（G1）考点：过河问题——1,2,5,10 四人最短 17。

解析：本题考查过河问题。经典贪心：快者结对送慢者。$1,2$ 过（$2$）$\to 1$ 回（$1$）$\to 5,10$ 过（$10$）$\to 2$ 回（$2$）$\to 1,2$ 过（$2$），共 $17$。每轮比较「两快送两慢（$2b{+}a{+}z$）」与「最快陪两慢（$2a{+}y{+}z$）」取小。此题为经典面试模型，大纲未明列、初赛偶见，解析关联即可。

排除法：B 答 $19$ 的人用了「最快轮流陪」的单一方案没比较；D 答 $12$ 的人漏了回程计时；A 答 $28$ 的人让最慢者来回走。

考点：货仓选址的策略（G2）。

（G2）考点：货仓选址的策略——货仓建在中位数，{2,5,7,16} 距离和 16。

解析：本题考查货仓选址的策略。一维点到各定点的距离和在中位数处最小：位置左移，右边多的商店每人加一减不动；偶数个点时中间整段任意位置等价。L2 实测 $\{2,5,7,16\}$ 建在 $6$ 距离和 $16$。

排除法：D 选最左端 $2$ 的人偏到一侧距离和 $20$ 更大；C 选最右端 $16$ 的人同样偏离；A 选平均值 $7.5$ 的人在偶数个商店时恰好也落中位段（本题 $7.5$ 也得 $16$），但一般情形均值不保证——中位数才是正解。

考点：种树问题（G3）。

（G3）考点：种树问题——按右端点处理，缺树则种右端点。

解析：本题考查种树问题。与区间选点同构：树要尽量让后续区间「顺便」用上，种在当前区间右端点最能兼顾右侧。O2 实测 $\{[1,3],[2,5],[4,6]\}$ 种 $2$ 棵（$3$ 与 $6$）。

排除法：A 选左端点各种一棵的人对右延区间照顾不足；D 选中点的人对端点对齐的区间效率低；C 选每个位置都种的人没有数量约束概念。

考点：双窗口排队（G4）。

（G4）考点：双窗口排队——每人选更早空闲窗口，第 4 人完成于 5。

解析：本题考查双窗口排队。模拟：窗口 $A$（$3$）与 $B$（$2$），四人依次（各耗时 $1$）到达选早空闲者——用时推演后第 $4$ 人（下标 $3$）完成于 $5$。贪心规则「选更早空闲」在双机调度里就是列表调度，简单常用。

排除法：C 答 $4$ 的人少算一轮排队；D 答 $6$ 的人把窗口耗时全当 $3$；B 答 $8$ 的人把四人全排进了慢窗口。

考点：跳跃游戏（G5）。

（G5）考点：跳跃游戏——{2,3,1,1,4} 最少 2 步。

解析：本题考查跳跃游戏。贪心维护「当前步可达边界」与「下一步最远可达」：边界一到即步数加一。$\{2,3,1,1,4\}$：第一步最远到下标 $3$，第二步从 $3$ 可到 $4$，共 $2$ 步（M3 代码形态）。

排除法：D 答 $3$ 的人每步只跳一格邻位没用满跨度；A 答 $1$ 的人以为首格 $2$ 直达末格（$2$ 只到下标 $2$）；C 答 $4$ 的人逐格跳。

考点：拼数综合（G6）。

（G6）考点：拼数综合——{32,3,321} 最小 321323、最大 332321。

解析：本题考查拼数综合。按 $x{+}y$ 与 $y{+}x$ 的字典序排序一遍即可同时服务最小与最大（比较器方向相反）。最小序为 $321,32,3$，最大序为 $3,32,321$。若按数值排序会得到错误开头。

排除法：B 答 332321 与 321323 的人把最小与最大整个对调，比较器方向装反；D 答 321323 与 323213 的人最大拼次序错，$3$ 应排在 $32$ 之前；A 答 323213 与 332321 的人最小拼按数值排序走错，正确最小是 321323。

考点：贪心缺乏全局观（H1）。

（H1）考点：贪心缺乏全局观——每步占资源可能堵死后续更优组合。

解析：本题考查贪心缺乏全局观。贪心眼睛只看当前步：01 背包先装大件、活动安排选长活动，都是「此刻占优、后路被断」。这正是需要反例意识（A6）与 DP 备胎（E1）的根源。

排除法：A 选代码太长的人谈的是可读性不是算法性质；C 选排序方向写反的人谈的是实现 bug 不是策略缺陷；B 选没用递归的人谈的是实现形式。

考点：排序键选错（H2）。

（H2）考点：排序键选错——按开始时间排活动，长活动占掉全程。

解析：本题考查排序键选错。开始早不代表结束早：$(1,8)$ 开始最早却横贯全程。按开始排序先选它，后面全冲突。正确键是结束时间（B2）。P5 用具体数据展示两种排序的差距。

排除法：B 选会越界的人把逻辑错误错报成内存错误；A 选更慢的人两个键排序速度一样；C 选等价的人被 $(1,8)$ 型数据直接否证。

考点：找零贪心的条件（H3）。

（H3）考点：找零贪心的条件——面额层层整倍嵌套才保证贪心最优。

解析：本题考查找零贪心的条件。人民币 $100=2\times50$、$50=2\times20{+}10$……大面额能被小面额「无浪费」地拼出，任何贪心选择都可被整体等价替换。$\{1,3,4\}$ 缺这种嵌套（$4$ 与 $3$ 不整倍），贪心翻车（F5）。

排除法：C 选任何面额都满足的人被 $4$ 与 $3$ 的反例打脸；B 选质数的人方向反了——质数之间更不整倍；D 选有 $1$ 就行的人只保证了「能找开」不保证「找得最优」。

考点：合并果子与哈夫曼（H4）。

（H4）考点：合并果子与哈夫曼——每次合并最小两堆即建哈夫曼树，总代价即 WPL。

解析：本题考查合并果子与哈夫曼。堆权是叶权，每次合并是建树中两最小节点结合，合并代价之和恰等于带权路径长度。L1 的 $\{1,2,9\}$ 代价 $15$ 即该组权的哈夫曼 WPL。2021 年真题考过「哈夫曼编码本质是贪心」——两个知识点在此汇合。

排除法：A 选毫无关系的人没看出小根堆操作与哈夫曼构造逐步同构；D 选哈夫曼合并最大的人方向全反；C 选每次全排序的人把实现细节（小根堆可免全排序）当成了必需。

考点：贪心综合判断（H5）。

（H5）考点：贪心综合判断——贪心不可回头，成败全在策略。

解析：本题考查贪心综合判断。贪心没有回溯机制，走错一步整条链就错；所以重心前移到「设计并验证策略」。四条选项各对应一个常见误解，逐一排除即得。

排除法：C 选可中途反悔的人描述的是回溯；D 选正确性靠代码长度保证的人把工程量当数学；B 选所有最优化都有贪心解的人高估了它的疆域（01 背包、TSP 都是反例）。

考点：找零钱的张数（I1）。

（I1）考点：找零钱的张数——87 元贪心 6 张。

解析：本题考查找零钱的张数。逐面额削：$87-50=37$、$37-20=17$、$17-10=7$、$7-5=2$、$2-1-1=0$，共 $6$ 张。双重循环是面额贪心的标准代码形态。

排除法：D 答 $5$ 的人少算了一张一元；C 答 $87$ 的人全用一元面额；B 答 $4$ 的人漏了找零尾数。

考点：找零钱的过程（I2）。

（I2）考点：找零钱的过程——63 元依次输出 50 10 1 1 1 共 5 张。

解析：本题考查找零钱的过程。$63$ 削 $50$ 剩 $13$、削 $10$ 剩 $3$、再三个 $1$：输出 50 10 1 1 1，共 $5$ 张。过程题考的是对双重循环执行序的追踪。

排除法：B 答张数 $4$ 的人把三个 $1$ 数成两个（剩 $3$ 元恰要 $3$ 张一元）；A 答 20 20 20 1 1 1 与 $6$ 张的人没用最大面额优先，白白多花一张；C 答 50 10 3 的人把余额 $3$ 当成了面额。

考点：每次选最大（I3）。

（I3）考点：每次选最大——两次选出 9 与 7。

解析：本题考查每次选最大。$\{3,7,1,9,4\}$ 首轮 $9$、次轮 $7$。若用打擂台实现是 $O(n)$ 每轮；排序实现一轮 $O(n\log_2 n)$ 全序拿下（I4）。

排除法：A 答 $9$ 与 $4$ 的人次轮把次大错认成末元素；D 答 $7$ 与 $9$ 的人把顺序反了——最大先出；B 答 $3$ 与 $7$ 的人首轮就选错。

考点：排序后取最大（I4）。

（I4）考点：排序后取最大——降序前二和为 16。

解析：本题考查排序后取最大。降序排序后 $a[0]=9$、$a[1]=7$，和 $16$。排序一次，前 $k$ 大、后 $k$ 小全部就位，是最值贪心的快捷通道。

排除法：C 答 $9$ 的人只取了一个；D 答 $24$ 的人把全部元素求和；A 答 $13$ 的人次大取成了 $4$。

考点：两端取较小（I5）。

（I5）考点：两端取较小——{5,2,8,3,6} 输出 5 2 6 3 8。

解析：本题考查两端取较小。双指针从两端向内，每步输出较小端：$5$（左）$\to 2$（左）$\to 6$（右）$\to 3$（左）$\to 8$。相等时取左（<=）。这是双指针与贪心结合的入门形态。

排除法：B 答 2 3 5 6 8 的人输出成了排序结果；A 答原序的人没做选择；D 答 6 3 8 2 5 的人全程取右端。

考点：贪心与枚举同题（I6）。

（I6）考点：贪心与枚举同题——选两数和最大：枚举与贪心殊途同归。

解析：本题考查贪心与枚举同题。「选两个数使和最大」没有牵制结构（选了最大的不妨碍选次大），贪心排序取前二与枚举所有数对同答案。小数据上对拍两版输出一致，正是 D5 对拍法的工作方式。

排除法：A 选一定不同的人在无牵制问题上两法必同；C 选贪心输出更大的人忘了最优解唯一；B 选枚举一定超时的人没算 $n\le1000$ 时 $n^2$ 完全可过。

考点：最值贪心代码（I7）。

（I7）考点：最值贪心代码——不相邻取数每次取最大封锁邻居，{3,7,1,9,4} 得 16。

解析：本题考查最值贪心代码。先取 $9$ 并封锁其邻居 $1,4$，再取 $7$，得 $16$。此数据贪心恰好最优。一般情形「每次取最大」的不相邻取数有反例（如 $\{2,3,2\}$ 取 $3$ 只得 $3$，而 $2+2=4$），稳妥做法是 DP。

排除法：D 先取 $3$ 再取 $1$ 的人没走「当前最大优先」的规则；C 以为先取 $7$ 后取 $9$ 被拒的人搞错了封锁对象——$9$ 与 $7$ 并不相邻，两个都能取到；A 选取全部五个的人违反不相邻约束。

考点：活动安排计数（J1）。

（J1）考点：活动安排计数——六场活动按结束贪心选 3 场。

解析：本题考查活动安排计数。按结束排序：$(1,3),(2,5),(4,7),(1,8),(6,9),(8,10)$；选 $(1,3)$（last=3）$\to (2,5)$ 冲突 $\to (4,7)$ 选（last=7）$\to (1,8)$ 冲突 $\to (6,9)$ 冲突 $\to (8,10)$ 选。共 $3$ 场。

排除法：C 答 $4$ 场的人把某个冲突活动算了进去；A 答 $2$ 场的人多判了一次冲突；B 答 $6$ 场的人完全没做冲突检查。

考点：区间选点数（J2）。

（J2）考点：区间选点数——五个区间最少 2 个点。

解析：本题考查区间选点数。按右端排序 $(2,3),(1,4),(3,5),(5,7),(6,8)$：区间 $(2,3)$ 缺点放 $3$——覆盖 $(1,4)$ 与 $(3,5)$（都含 $3$）；$(5,7)$ 缺点放 $7$——覆盖 $(6,8)$。共 $2$ 点。

排除法：B 答 $3$ 的人没利用 $3$ 同时覆盖三个区间；D 答 $4$ 的人近乎每区间一点；C 答 $5$ 的人完全没共享。

考点：区间覆盖数（J3）。

（J3）考点：区间覆盖数——盖 [0,10] 最少 3 条。

解析：本题考查区间覆盖数。从 $0$ 出发：左端 $\le0$ 的只有 $(0,3)$，盖到 $3$；左端 $\le3$ 中右端最远是 $(3,8)$，盖到 $8$；左端 $\le8$ 中 $(6,10)$ 最远到 $10$。共 $3$ 条。

排除法：B 答 $2$ 条的人中间接不上（没有线段同时从 $\le0$ 跨到 $\ge10$）；A 答 $4$ 条的人某步没取最远右端多走一步；C 答 $6$ 条的人全用了。

考点：最少教室数（J4）。

（J4）考点：最少教室数——五场活动 2 间教室。

解析：本题考查最少教室数。按开始排序 $(1,4),(2,5),(4,6),(5,8),(7,9)$：$(1,4)$ 开教室一（空于 $4$）；$(2,5)$ 开教室二（空于 $5$）；$(4,6)$ 复用教室一（$4\ge4$，空于 $6$）；$(5,8)$ 复用教室二（空于 $8$）；$(7,9)$ 复用教室一（$7\ge6$）。共 $2$ 间。

排除法：D 答 $3$ 间的人把「结束即空闲」多留了一拍；B 答 $4$ 间的人漏了复用；A 答 $5$ 间的人每场一间没做任何调度。

考点：区间合并计数（J5）。

（J5）考点：区间合并计数——五个区间合并后剩 3 个。

解析：本题考查区间合并计数。排序后 $(1,3),(2,5)$ 相接合并为 $[1,5]$；$(6,8),(8,10)$ 端点相接合并为 $[6,10]$；$(12,13]$ 独立。共 $3$ 个。相接（右端等于下一段左端）算重叠是本题口径，丢等号见 P5。

排除法：B 答 $5$ 个的人一个都没并；D 答 $2$ 个的人把 $[1,5]$ 与 $[6,10]$ 也并了（中间有断开）；C 答 $4$ 个的人只并了一对。

考点：按右端点排序输出（J6）。

（J6）考点：按右端点排序输出——右端点序 3 5 7 8 9 10。

解析：本题考查按右端点排序输出。六区间右端点 $3,5,7,8,9,10$ 升序即答案——区间的其他信息（左端、编号）不参与输出，考的是「键排序」这步本身的执行。

排除法：C 答 1 2 4 1 6 8 的人输出成了左端点序；D 答降序的人方向反；B 答 1 1 2 4 6 8 的人把左端排序后又弄乱了次序。

考点：选中活动判定（J7）。

（J7）考点：选中活动判定——第二个选中是 (4,7)。

解析：本题考查选中活动判定。首选拿 $(1,3)$；接着扫描 $(2,5)$（开始 $2<$ last $3$ 冲突跳过）、$(4,7)$（$4\ge3$ 选中）。第二个选中即 $(4,7)$。追踪「谁被跳过」是活动贪心代码题的常考点。

排除法：A 选 $(2,5)$ 的人没做冲突检查；B 选 $(1,8)$ 的人把它当成了第一个或忘了已选 $(1,3)$；D 选 $(6,9)$ 的人跳过了更早结束的 $(4,7)$。

考点：部分背包最大价值（K1）。

（K1）考点：部分背包最大价值——C=6 装得 8.5。

解析：本题考查部分背包最大价值。单位价值 $1.5,1.33,1.25$：整装 $w{=}2$ 与 $w{=}3$（价值 $7$），剩容量 $1$ 从 $w{=}2$ 的物品割一半（价值 $1.5$），共 $8.5$。可分割让「寸土寸金」成立，贪心最优。

排除法：D 答 $8$ 的人没割最后一件浪费了剩余容量；C 答 $9$ 的人把三件全装总重 $9$ 超容；A 答 $7$ 的人忘了最后还能装 $1$ 单位。

考点：排队接水等待和（K2）。

（K2）考点：排队接水等待和——{3,1,2} 短者先接等待和 4。

解析：本题考查排队接水等待和。顺序 $1,2,3$：第 $2$ 人等 $1$、第 $3$ 人等 $1{+}2=3$，和 $4$。若按原序 $3,1,2$：等待 $0+3+4=7$——排序省下近一半。

排除法：A 答 $5$ 的人按 $1,3,2$ 或类似次序排没取最优序；C 答 $6$ 的人按 $2,1,3$ 排；B 答 $3$ 的人只算了前两人的等待。

考点：双窗口排队（K3）。

（K3）考点：双窗口排队——第 4 人完成于 5。

解析：本题考查双窗口排队。模拟选早空闲：前几人轮流填窗口，推演得第 $4$ 人（下标 $3$）完成于 $5$。规则简单，考的是逐时刻推演不出错。

排除法：C 答 $4$ 的人少算一次窗口耗时；D 答 $6$ 的人把快窗口当慢窗口；B 答 $7$ 的人全排在慢窗口后面。

考点：零一背包贪心结果（K4）。

（K4）考点：零一背包贪心结果——贪心 7，DP 8。

解析：本题考查零一背包贪心结果。单位价值序装 $w{=}2$（$v{=}3$）、$w{=}3$（$v{=}4$）后剩容量 $1$，总 $7$；DP 的最优组合 $w{=}2{+}4$ 价值 $8$。同一组数据三处出现（E5 概念、K4 代码、P6 对比）——从三个角度吃透这个经典反例。

排除法：A 答 $8$ 的人给的是 DP 结果，贪心走不到；B 答 $9$ 的人超容；D 答 $6$ 的人某件的价值记错。

考点：删数问题输出（K5）。

（K5）考点：删数问题输出——15763 删 2 个得 153。

解析：本题考查删数问题输出。第一轮扫到 $7>6$ 删 $7$ 得 $1563$；第二轮 $6>3$ 删 $6$ 得 $153$。每删一次重新从头扫——峰被削掉后新的下降沿可能出现在更前面。

排除法：B 答 $157$ 的人删成了后两位；C 答 $563$ 的人删了首位；D 答 $123$ 的人改了数字不是删除。