1. 从一道经典题看贪心算法的实战拆解陶陶摘苹果这个题目很多刷过算法题的朋友应该都不陌生。原版是入门级的模拟题而升级版加入了体力消耗这个约束条件一下子把难度从照着题意写循环拉到了需要想清楚策略的层面。我最近在帮几个刚入门算法竞赛的朋友梳理贪心专题重新把这道题拿出来仔细拆了一遍发现它其实是一个非常典型的排序加贪心教学样本值得好好聊一聊。这道题的核心场景是这样的院子里有一棵苹果树树上有若干个苹果每个苹果有自己的高度。陶陶有一个椅子可以踩椅子高度加上他自身能够到的高度构成了一个能够摘到苹果的高度上限。但升级版的关键在于陶陶的体力是有限的摘每个苹果需要消耗一定的力气而他的总体力有一个上限。目标是在体力允许的范围内摘到尽可能多的苹果。这个问题的本质是什么是在一个约束条件下求最优解。具体来说就是在体力约束下最大化摘苹果的数量。每个苹果的代价是消耗的体力收益是数量加一。所有苹果的收益都一样但代价不同。这种情况下最优策略非常明确优先摘那些消耗体力最少的苹果。这就是贪心算法的经典应用场景。为什么贪心在这里是对的因为每个苹果带来的收益完全相同都是让总数加一。既然收益一样那当然要选代价最小的。这个逻辑和用有限的预算买尽可能多的商品是一样的——如果每件商品的价值对你来说都一样你肯定先买便宜的那个。这个直觉非常朴素但背后其实有严格的数学证明支撑后面我会详细展开。适合谁来读这篇内容如果你刚开始接触算法竞赛对贪心算法还停留在好像懂但不太确定的阶段那这道题非常适合作为你的第一个贪心实战案例。如果你已经有一定基础也可以看看我在实现细节和边界处理上的一些经验说不定能帮你避开几个容易踩的坑。2. 问题建模与贪心策略的完整推导2.1 如何把生活场景翻译成算法语言拿到任何一道算法题第一步永远是建模。把生活中的描述翻译成计算机能处理的数学语言这一步做得好不好直接决定了后面的代码是否清晰、是否容易出错。先梳理输入信息。第一行通常给出两个数字苹果的数量n和陶陶的体力上限s。第二行给出两个数字椅子高度a和陶陶自身能够到的最大高度b。接下来n行每行两个数字苹果距离地面的高度和摘下这个苹果需要消耗的体力。这里有一个容易忽略的细节陶陶能够到的最大高度是椅子高度加上他自身的身高能够到的高度。也就是说只有高度不超过ab的苹果才是可摘的。那些高度超过ab的苹果不管体力够不够都够不着直接排除。所以第一步筛选就很明确了遍历所有苹果把高度大于ab的苹果过滤掉。剩下的苹果才是真正参与后续决策的候选集合。过滤完之后问题就变成了在体力上限s的约束下从候选苹果中选出尽可能多的苹果使得总消耗不超过s。每个苹果的消耗已知收益都是1。2.2 为什么贪心策略在这个场景下是最优的很多人学贪心的时候最大的困惑就是我怎么知道贪心是对的会不会存在某种情况我按照贪心策略选了结果反而不是最优这个问题在这道题里可以非常清晰地回答。假设我们有一组候选苹果每个苹果的体力消耗分别是c1、c2、c3……我们的目标是在总消耗不超过s的前提下选出的苹果数量最多。考虑任意一个最优解假设它选了k个苹果。如果这k个苹果不是消耗最小的k个那么一定存在一个没被选中的苹果它的消耗比某个被选中的苹果更小。我们把那个消耗大的换成这个消耗小的总消耗只会减少数量不变所以仍然是一个合法解而且可能还能再塞进去更多苹果。这就说明一定存在一个由消耗最小的若干苹果组成的最优解。这个证明思路叫做交换论证法是证明贪心正确性最常用的手段。用大白话说就是如果存在一个最优方案没有选最便宜的那些那我总能用更便宜的替换掉贵的结果不会变差。所以直接选最便宜的就行了。注意贪心算法不是万能的。它之所以在这道题里成立是因为所有苹果的收益完全相同。如果每个苹果的价值不一样比如有的苹果值10分有的值1分那就不能简单按消耗排序了需要用到动态规划或者其他方法。这一点在后续做题时一定要警惕。2.3 排序策略的选择与实现细节确定了贪心策略之后实现上最关键的一步就是排序。把所有候选苹果按照消耗体力从小到大排序然后从最小的开始逐个尝试摘取直到体力不够为止。排序算法用标准库提供的就行时间复杂度是O(n log n)对于这道题的数据规模来说完全够用。不需要手写排序除非题目特别要求。但这里有一个实现上的小细节值得注意我们其实不需要把所有苹果的信息都存下来再排序。可以在读入数据的时候就直接过滤掉够不着的苹果只把够得着的苹果的体力消耗存进一个数组然后对这个数组排序。这样既节省空间又让代码逻辑更清晰。具体来说用一个动态数组或者固定大小的数组来存储候选苹果的体力消耗值。每读入一个苹果判断高度是否在可达范围内如果是就加入数组。读完之后对数组排序然后从小到大遍历用一个累加器记录当前已消耗的体力只要加上下一个苹果的消耗不超过体力上限就摘计数器加一否则停止。这个流程非常清晰代码量也不大但每一步都有它的道理。过滤是减少问题规模排序是确定贪心顺序遍历累加是执行决策。三步走下来问题就解决了。3. 完整代码实现与逐行解析3.1 核心代码框架的搭建下面用C来完整实现这道题的解法。选择C是因为它在算法竞赛中最常用标准库的排序函数也非常方便。如果你习惯用Python或Java逻辑完全一样只是语法不同。#include iostream #include algorithm #include vector using namespace std; int main() { int n, s; cin n s; int a, b; cin a b; int reachHeight a b; vectorint costs; for (int i 0; i n; i) { int height, cost; cin height cost; if (height reachHeight) { costs.push_back(cost); } } sort(costs.begin(), costs.end()); int count 0; int totalCost 0; for (int i 0; i (int)costs.size(); i) { if (totalCost costs[i] s) { totalCost costs[i]; count; } else { break; } } cout count endl; return 0; }这段代码的逻辑非常直白。先读入苹果总数和体力上限再读入椅子高度和陶陶能够到的高度计算出可达高度上限。然后逐个读入苹果信息够得着的就把体力消耗存进数组。排序之后从小到大尝试摘取能摘就摘摘不动就停。3.2 关键步骤的逐行拆解与参数说明让我把几个关键步骤再展开说一下因为很多初学者看代码觉得好像懂了但自己写的时候就会在细节上卡住。第一处是int reachHeight a b;。这里把椅子高度和陶陶自身能够到的高度相加得到实际可达的最大高度。这个值在后续每次判断苹果是否可摘时都会用到所以提前算好存起来避免重复计算。虽然计算本身很便宜但这是一个好习惯。第二处是if (height reachHeight)。注意这里用的是小于等于不是小于。题目说的是能够到的高度那么恰好等于这个高度的苹果也是能够到的。这种边界条件在算法题里非常容易出错写的时候一定要对照题目描述确认清楚。第三处是sort(costs.begin(), costs.end());。默认是从小到大排序正好符合我们的贪心策略。如果你用的是其他语言比如Python的sorted()函数或者Java的Arrays.sort()默认也都是升序不需要额外指定比较函数。第四处是循环中的判断if (totalCost costs[i] s)。这里先判断加上当前苹果的消耗是否会超过体力上限如果不会就加上去并计数否则直接跳出循环。为什么可以直接跳出因为数组已经排好序了后面的苹果消耗只会更大当前这个都摘不了后面的更不可能摘得了。这个提前终止是排序带来的额外好处省去了不必要的遍历。3.3 时间与空间复杂度的实际评估这道题的时间复杂度主要由排序决定是O(n log n)。过滤和遍历都是O(n)的被排序的复杂度主导。对于通常的题目数据规模比如n在几千到几万之间这个复杂度绰绰有余。空间复杂度是O(n)用来存储候选苹果的体力消耗。如果题目对空间有严格限制也可以在原数组上操作但一般来说没必要为了省这点空间牺牲代码的可读性。实际跑下来即使n达到十万级别这段代码也能在几十毫秒内完成。当然如果n更大比如到百万级别可能需要考虑更高效的排序或者用计数排序之类的线性排序方法但那已经超出了这道题的范围。实操心得在算法竞赛中除非题目明确卡常数或者数据规模极大否则优先选择代码清晰、不易出错的写法。过早优化是万恶之源这句话在竞赛中同样适用。先保证正确性再考虑性能。4. 常见错误与调试经验实录4.1 新手最容易踩的五个坑这道题虽然思路简单但实际写的时候还是有不少容易出错的地方。我整理了五个最常见的错误每一个都是我或者我身边的朋友实际踩过的。第一个坑是忘记过滤够不着的苹果。有些人读完题目之后直接对所有苹果排序然后按消耗从小到大摘完全忽略了高度限制。这样写出来的代码在样例上可能碰巧能过但遇到有苹果高度超过可达上限的测试数据就会出错。过滤这一步绝对不能省。第二个坑是边界条件写错。前面提到过高度判断应该是小于等于而不是小于。同样体力判断也应该是totalCost costs[i] s而不是 s。恰好用完体力也是合法的这一点要特别注意。第三个坑是排序之后忘记用排好序的数组。有些人排序了但后面遍历的时候还是用原来的顺序或者排序和遍历用的不是同一个数组。这种错误很隐蔽因为代码不会报错只是结果不对。第四个坑是体力累加变量的类型。如果体力上限和单个苹果的消耗都比较大累加过程中可能会超出int的范围。虽然这道题的数据规模通常不会导致溢出但养成用long long的习惯是好的。特别是在竞赛中因为溢出丢分太亏了。第五个坑是输入格式理解错误。有些题目会在一行里给出多个数字有些会分行给出。虽然用cin或scanf读入的时候不关心换行但如果你用其他方式读入比如按行读取再解析就需要特别注意。这道题的标准输入格式是明确的但竞赛中经常有题目在输入格式上做文章读题的时候一定要仔细。4.2 调试技巧与验证方法写完代码之后怎么验证最直接的方法是用题目提供的样例数据跑一遍看看输出是否一致。但样例通常很简单只能验证基本逻辑不能覆盖所有边界情况。我习惯自己构造几组测试数据来验证。比如所有苹果都够不着的情况应该输出0体力刚好够摘一个苹果的情况体力刚好差一点不够摘任何一个苹果的情况所有苹果都能摘但体力只够摘一部分的情况。这些边界情况能过代码的健壮性就基本没问题了。另外一个小技巧是在代码里临时加一些输出语句把过滤后的候选数组打印出来看看是不是符合预期。确认无误后再把这些调试语句删掉。这个方法虽然原始但在排查逻辑错误的时候非常有效。如果提交之后出现错误先看是答案错误还是运行超时。答案错误通常是逻辑问题需要重新审视贪心策略和边界条件。运行超时则是复杂度问题需要优化算法。这道题一般来说不会超时除非用了非常低效的排序或者多重循环。4.3 从这道题延伸出的同类问题掌握了这道题的解法之后可以尝试一些变体来巩固理解。比如如果每个苹果有不同的价值怎么在体力约束下最大化总价值这就变成了一个0-1背包问题需要用动态规划来解。如果苹果可以部分摘取比如摘一半消耗一半体力那就是分数背包问题贪心策略又适用了但排序的依据变成了性价比而不是绝对消耗。再比如如果陶陶可以多次休息恢复体力但休息次数有限怎么安排摘取顺序这就涉及到了更复杂的决策过程可能需要用到动态规划或者搜索。这些变体在算法竞赛中都很常见但它们的核心思想都可以从这道简单的贪心题中找到影子。把基础打牢后面遇到复杂问题的时候才能快速找到切入点。常见错误症状解决方法未过滤够不着的苹果部分测试点答案偏大读入时判断高度只存可达苹果边界条件用小于而非小于等于特定测试点答案偏小仔细读题确认是否包含等号排序后未使用有序数组结果随机或偏小检查遍历的是否为排序后的数组体力累加溢出大数测试点答案错误使用long long类型输入格式解析错误程序崩溃或结果异常严格按照题目格式读入5. 贪心思维的实战价值与进阶方向5.1 贪心算法在真实开发中的影子很多人觉得算法竞赛里的题目和实际开发脱节但贪心思维在工程实践中其实非常常见。举几个例子任务调度中当所有任务的收益相同时优先执行耗时短的任务能让单位时间内完成的任务数最多这就是贪心。内存分配中当所有内存块的价值相同时优先分配最小的能满足需求的内存块能减少碎片这也是贪心。网络带宽分配、磁盘调度、缓存淘汰策略背后都有贪心思想的影子。这道摘苹果的题目本质上就是一个资源分配问题。体力是有限的资源苹果是需要消耗资源才能获取的收益。当收益均等时优先把资源分配给成本最低的选项这个原则在任何资源分配场景中都适用。理解了这一点你就不会觉得这道题只是一道竞赛题了。它训练的是一种思维方式在面对有限资源和多个选项时如何快速做出最优或接近最优的决策。这种思维方式在你写业务代码、做系统设计、甚至安排日常工作时都能派上用场。5.2 什么时候贪心会失效贪心虽然好用但它有明确的适用条件。前面提到过当收益不均等时简单贪心可能失效。更一般地说贪心算法要求问题具有贪心选择性质和最优子结构性质。前者意味着局部最优选择能导致全局最优解后者意味着问题的最优解包含子问题的最优解。判断一道题能不能用贪心一个实用的方法是尝试构造反例。如果你能找到一个反例说明贪心策略不成立如果你尝试了很多种情况都找不到反例那贪心可能是对的但最好还是用交换论证法严格证明一下。在竞赛中时间有限的情况下如果你对贪心策略有较强的直觉可以先写出来提交试试。如果过了说明策略正确如果没过再换思路。但这种方法有风险因为有些题目的反例很隐蔽你可能碰巧过了样例但实际是错的。所以平时训练的时候还是要养成严格证明的习惯。5.3 从贪心到动态规划的进阶路径如果你已经掌握了这道题的贪心解法下一步可以尝试把它改成动态规划来解即使收益均等的情况下也可以用DP只是没必要。但通过对比两种解法你能更深刻地理解贪心和DP的区别与联系。DP的解法是这样的定义状态dp[i][j]表示前i个苹果在体力j的限制下能摘到的最大数量。转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-cost[i]] 1)。这个方程的意思是对于第i个苹果要么不摘继承前i-1个苹果在体力j下的结果要么摘那么前i-1个苹果只能用j-cost[i]的体力结果加一。取两者的较大值。这个DP的时间复杂度是O(ns)空间复杂度也是O(ns)可以用滚动数组优化到O(s)。当s不大的时候DP是可行的但当s很大的时候DP就会超时而贪心的O(n log n)依然很快。这就是为什么在收益均等的情况下贪心是更好的选择。通过这个对比你能清楚地看到贪心利用问题的特殊结构收益均等来简化求解而DP则是一种更通用但代价更高的方法。在实际问题中如果能用贪心优先用贪心贪心不行再考虑DP。我在实际教学中的体会是很多初学者觉得贪心太简单了没什么好学的急着去学DP、图论、数据结构。但恰恰是贪心这种看似简单的思想最能锻炼你对问题结构的洞察力。你能不能一眼看出这个问题可以用贪心你能不能严格证明贪心策略的正确性这些能力比记住几个DP转移方程重要得多。把这道摘苹果的题目吃透比刷十道似懂非懂的难题更有价值。后续可以尝试找一些贪心和DP都能解的题目分别用两种方法实现对比它们的思路差异和性能表现这种对比练习对建立算法直觉非常有帮助。 
长河君 · 2026/10/15 1:35:17 · 阅读 1.2k 贪心算法实战：从陶陶摘苹果看排序与资源分配
1. 从一道经典题看贪心算法的实战拆解陶陶摘苹果这个题目很多刷过算法题的朋友应该都不陌生。原版是入门级的模拟题而升级版加入了体力消耗这个约束条件一下子把难度从照着题意写循环拉到了需要想清楚策略的层面。我最近在帮几个刚入门算法竞赛的朋友梳理贪心专题重新把这道题拿出来仔细拆了一遍发现它其实是一个非常典型的排序加贪心教学样本值得好好聊一聊。这道题的核心场景是这样的院子里有一棵苹果树树上有若干个苹果每个苹果有自己的高度。陶陶有一个椅子可以踩椅子高度加上他自身能够到的高度构成了一个能够摘到苹果的高度上限。但升级版的关键在于陶陶的体力是有限的摘每个苹果需要消耗一定的力气而他的总体力有一个上限。目标是在体力允许的范围内摘到尽可能多的苹果。这个问题的本质是什么是在一个约束条件下求最优解。具体来说就是在体力约束下最大化摘苹果的数量。每个苹果的代价是消耗的体力收益是数量加一。所有苹果的收益都一样但代价不同。这种情况下最优策略非常明确优先摘那些消耗体力最少的苹果。这就是贪心算法的经典应用场景。为什么贪心在这里是对的因为每个苹果带来的收益完全相同都是让总数加一。既然收益一样那当然要选代价最小的。这个逻辑和用有限的预算买尽可能多的商品是一样的——如果每件商品的价值对你来说都一样你肯定先买便宜的那个。这个直觉非常朴素但背后其实有严格的数学证明支撑后面我会详细展开。适合谁来读这篇内容如果你刚开始接触算法竞赛对贪心算法还停留在好像懂但不太确定的阶段那这道题非常适合作为你的第一个贪心实战案例。如果你已经有一定基础也可以看看我在实现细节和边界处理上的一些经验说不定能帮你避开几个容易踩的坑。2. 问题建模与贪心策略的完整推导2.1 如何把生活场景翻译成算法语言拿到任何一道算法题第一步永远是建模。把生活中的描述翻译成计算机能处理的数学语言这一步做得好不好直接决定了后面的代码是否清晰、是否容易出错。先梳理输入信息。第一行通常给出两个数字苹果的数量n和陶陶的体力上限s。第二行给出两个数字椅子高度a和陶陶自身能够到的最大高度b。接下来n行每行两个数字苹果距离地面的高度和摘下这个苹果需要消耗的体力。这里有一个容易忽略的细节陶陶能够到的最大高度是椅子高度加上他自身的身高能够到的高度。也就是说只有高度不超过ab的苹果才是可摘的。那些高度超过ab的苹果不管体力够不够都够不着直接排除。所以第一步筛选就很明确了遍历所有苹果把高度大于ab的苹果过滤掉。剩下的苹果才是真正参与后续决策的候选集合。过滤完之后问题就变成了在体力上限s的约束下从候选苹果中选出尽可能多的苹果使得总消耗不超过s。每个苹果的消耗已知收益都是1。2.2 为什么贪心策略在这个场景下是最优的很多人学贪心的时候最大的困惑就是我怎么知道贪心是对的会不会存在某种情况我按照贪心策略选了结果反而不是最优这个问题在这道题里可以非常清晰地回答。假设我们有一组候选苹果每个苹果的体力消耗分别是c1、c2、c3……我们的目标是在总消耗不超过s的前提下选出的苹果数量最多。考虑任意一个最优解假设它选了k个苹果。如果这k个苹果不是消耗最小的k个那么一定存在一个没被选中的苹果它的消耗比某个被选中的苹果更小。我们把那个消耗大的换成这个消耗小的总消耗只会减少数量不变所以仍然是一个合法解而且可能还能再塞进去更多苹果。这就说明一定存在一个由消耗最小的若干苹果组成的最优解。这个证明思路叫做交换论证法是证明贪心正确性最常用的手段。用大白话说就是如果存在一个最优方案没有选最便宜的那些那我总能用更便宜的替换掉贵的结果不会变差。所以直接选最便宜的就行了。注意贪心算法不是万能的。它之所以在这道题里成立是因为所有苹果的收益完全相同。如果每个苹果的价值不一样比如有的苹果值10分有的值1分那就不能简单按消耗排序了需要用到动态规划或者其他方法。这一点在后续做题时一定要警惕。2.3 排序策略的选择与实现细节确定了贪心策略之后实现上最关键的一步就是排序。把所有候选苹果按照消耗体力从小到大排序然后从最小的开始逐个尝试摘取直到体力不够为止。排序算法用标准库提供的就行时间复杂度是O(n log n)对于这道题的数据规模来说完全够用。不需要手写排序除非题目特别要求。但这里有一个实现上的小细节值得注意我们其实不需要把所有苹果的信息都存下来再排序。可以在读入数据的时候就直接过滤掉够不着的苹果只把够得着的苹果的体力消耗存进一个数组然后对这个数组排序。这样既节省空间又让代码逻辑更清晰。具体来说用一个动态数组或者固定大小的数组来存储候选苹果的体力消耗值。每读入一个苹果判断高度是否在可达范围内如果是就加入数组。读完之后对数组排序然后从小到大遍历用一个累加器记录当前已消耗的体力只要加上下一个苹果的消耗不超过体力上限就摘计数器加一否则停止。这个流程非常清晰代码量也不大但每一步都有它的道理。过滤是减少问题规模排序是确定贪心顺序遍历累加是执行决策。三步走下来问题就解决了。3. 完整代码实现与逐行解析3.1 核心代码框架的搭建下面用C来完整实现这道题的解法。选择C是因为它在算法竞赛中最常用标准库的排序函数也非常方便。如果你习惯用Python或Java逻辑完全一样只是语法不同。#include iostream #include algorithm #include vector using namespace std; int main() { int n, s; cin n s; int a, b; cin a b; int reachHeight a b; vectorint costs; for (int i 0; i n; i) { int height, cost; cin height cost; if (height reachHeight) { costs.push_back(cost); } } sort(costs.begin(), costs.end()); int count 0; int totalCost 0; for (int i 0; i (int)costs.size(); i) { if (totalCost costs[i] s) { totalCost costs[i]; count; } else { break; } } cout count endl; return 0; }这段代码的逻辑非常直白。先读入苹果总数和体力上限再读入椅子高度和陶陶能够到的高度计算出可达高度上限。然后逐个读入苹果信息够得着的就把体力消耗存进数组。排序之后从小到大尝试摘取能摘就摘摘不动就停。3.2 关键步骤的逐行拆解与参数说明让我把几个关键步骤再展开说一下因为很多初学者看代码觉得好像懂了但自己写的时候就会在细节上卡住。第一处是int reachHeight a b;。这里把椅子高度和陶陶自身能够到的高度相加得到实际可达的最大高度。这个值在后续每次判断苹果是否可摘时都会用到所以提前算好存起来避免重复计算。虽然计算本身很便宜但这是一个好习惯。第二处是if (height reachHeight)。注意这里用的是小于等于不是小于。题目说的是能够到的高度那么恰好等于这个高度的苹果也是能够到的。这种边界条件在算法题里非常容易出错写的时候一定要对照题目描述确认清楚。第三处是sort(costs.begin(), costs.end());。默认是从小到大排序正好符合我们的贪心策略。如果你用的是其他语言比如Python的sorted()函数或者Java的Arrays.sort()默认也都是升序不需要额外指定比较函数。第四处是循环中的判断if (totalCost costs[i] s)。这里先判断加上当前苹果的消耗是否会超过体力上限如果不会就加上去并计数否则直接跳出循环。为什么可以直接跳出因为数组已经排好序了后面的苹果消耗只会更大当前这个都摘不了后面的更不可能摘得了。这个提前终止是排序带来的额外好处省去了不必要的遍历。3.3 时间与空间复杂度的实际评估这道题的时间复杂度主要由排序决定是O(n log n)。过滤和遍历都是O(n)的被排序的复杂度主导。对于通常的题目数据规模比如n在几千到几万之间这个复杂度绰绰有余。空间复杂度是O(n)用来存储候选苹果的体力消耗。如果题目对空间有严格限制也可以在原数组上操作但一般来说没必要为了省这点空间牺牲代码的可读性。实际跑下来即使n达到十万级别这段代码也能在几十毫秒内完成。当然如果n更大比如到百万级别可能需要考虑更高效的排序或者用计数排序之类的线性排序方法但那已经超出了这道题的范围。实操心得在算法竞赛中除非题目明确卡常数或者数据规模极大否则优先选择代码清晰、不易出错的写法。过早优化是万恶之源这句话在竞赛中同样适用。先保证正确性再考虑性能。4. 常见错误与调试经验实录4.1 新手最容易踩的五个坑这道题虽然思路简单但实际写的时候还是有不少容易出错的地方。我整理了五个最常见的错误每一个都是我或者我身边的朋友实际踩过的。第一个坑是忘记过滤够不着的苹果。有些人读完题目之后直接对所有苹果排序然后按消耗从小到大摘完全忽略了高度限制。这样写出来的代码在样例上可能碰巧能过但遇到有苹果高度超过可达上限的测试数据就会出错。过滤这一步绝对不能省。第二个坑是边界条件写错。前面提到过高度判断应该是小于等于而不是小于。同样体力判断也应该是totalCost costs[i] s而不是 s。恰好用完体力也是合法的这一点要特别注意。第三个坑是排序之后忘记用排好序的数组。有些人排序了但后面遍历的时候还是用原来的顺序或者排序和遍历用的不是同一个数组。这种错误很隐蔽因为代码不会报错只是结果不对。第四个坑是体力累加变量的类型。如果体力上限和单个苹果的消耗都比较大累加过程中可能会超出int的范围。虽然这道题的数据规模通常不会导致溢出但养成用long long的习惯是好的。特别是在竞赛中因为溢出丢分太亏了。第五个坑是输入格式理解错误。有些题目会在一行里给出多个数字有些会分行给出。虽然用cin或scanf读入的时候不关心换行但如果你用其他方式读入比如按行读取再解析就需要特别注意。这道题的标准输入格式是明确的但竞赛中经常有题目在输入格式上做文章读题的时候一定要仔细。4.2 调试技巧与验证方法写完代码之后怎么验证最直接的方法是用题目提供的样例数据跑一遍看看输出是否一致。但样例通常很简单只能验证基本逻辑不能覆盖所有边界情况。我习惯自己构造几组测试数据来验证。比如所有苹果都够不着的情况应该输出0体力刚好够摘一个苹果的情况体力刚好差一点不够摘任何一个苹果的情况所有苹果都能摘但体力只够摘一部分的情况。这些边界情况能过代码的健壮性就基本没问题了。另外一个小技巧是在代码里临时加一些输出语句把过滤后的候选数组打印出来看看是不是符合预期。确认无误后再把这些调试语句删掉。这个方法虽然原始但在排查逻辑错误的时候非常有效。如果提交之后出现错误先看是答案错误还是运行超时。答案错误通常是逻辑问题需要重新审视贪心策略和边界条件。运行超时则是复杂度问题需要优化算法。这道题一般来说不会超时除非用了非常低效的排序或者多重循环。4.3 从这道题延伸出的同类问题掌握了这道题的解法之后可以尝试一些变体来巩固理解。比如如果每个苹果有不同的价值怎么在体力约束下最大化总价值这就变成了一个0-1背包问题需要用动态规划来解。如果苹果可以部分摘取比如摘一半消耗一半体力那就是分数背包问题贪心策略又适用了但排序的依据变成了性价比而不是绝对消耗。再比如如果陶陶可以多次休息恢复体力但休息次数有限怎么安排摘取顺序这就涉及到了更复杂的决策过程可能需要用到动态规划或者搜索。这些变体在算法竞赛中都很常见但它们的核心思想都可以从这道简单的贪心题中找到影子。把基础打牢后面遇到复杂问题的时候才能快速找到切入点。常见错误症状解决方法未过滤够不着的苹果部分测试点答案偏大读入时判断高度只存可达苹果边界条件用小于而非小于等于特定测试点答案偏小仔细读题确认是否包含等号排序后未使用有序数组结果随机或偏小检查遍历的是否为排序后的数组体力累加溢出大数测试点答案错误使用long long类型输入格式解析错误程序崩溃或结果异常严格按照题目格式读入5. 贪心思维的实战价值与进阶方向5.1 贪心算法在真实开发中的影子很多人觉得算法竞赛里的题目和实际开发脱节但贪心思维在工程实践中其实非常常见。举几个例子任务调度中当所有任务的收益相同时优先执行耗时短的任务能让单位时间内完成的任务数最多这就是贪心。内存分配中当所有内存块的价值相同时优先分配最小的能满足需求的内存块能减少碎片这也是贪心。网络带宽分配、磁盘调度、缓存淘汰策略背后都有贪心思想的影子。这道摘苹果的题目本质上就是一个资源分配问题。体力是有限的资源苹果是需要消耗资源才能获取的收益。当收益均等时优先把资源分配给成本最低的选项这个原则在任何资源分配场景中都适用。理解了这一点你就不会觉得这道题只是一道竞赛题了。它训练的是一种思维方式在面对有限资源和多个选项时如何快速做出最优或接近最优的决策。这种思维方式在你写业务代码、做系统设计、甚至安排日常工作时都能派上用场。5.2 什么时候贪心会失效贪心虽然好用但它有明确的适用条件。前面提到过当收益不均等时简单贪心可能失效。更一般地说贪心算法要求问题具有贪心选择性质和最优子结构性质。前者意味着局部最优选择能导致全局最优解后者意味着问题的最优解包含子问题的最优解。判断一道题能不能用贪心一个实用的方法是尝试构造反例。如果你能找到一个反例说明贪心策略不成立如果你尝试了很多种情况都找不到反例那贪心可能是对的但最好还是用交换论证法严格证明一下。在竞赛中时间有限的情况下如果你对贪心策略有较强的直觉可以先写出来提交试试。如果过了说明策略正确如果没过再换思路。但这种方法有风险因为有些题目的反例很隐蔽你可能碰巧过了样例但实际是错的。所以平时训练的时候还是要养成严格证明的习惯。5.3 从贪心到动态规划的进阶路径如果你已经掌握了这道题的贪心解法下一步可以尝试把它改成动态规划来解即使收益均等的情况下也可以用DP只是没必要。但通过对比两种解法你能更深刻地理解贪心和DP的区别与联系。DP的解法是这样的定义状态dp[i][j]表示前i个苹果在体力j的限制下能摘到的最大数量。转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-cost[i]] 1)。这个方程的意思是对于第i个苹果要么不摘继承前i-1个苹果在体力j下的结果要么摘那么前i-1个苹果只能用j-cost[i]的体力结果加一。取两者的较大值。这个DP的时间复杂度是O(ns)空间复杂度也是O(ns)可以用滚动数组优化到O(s)。当s不大的时候DP是可行的但当s很大的时候DP就会超时而贪心的O(n log n)依然很快。这就是为什么在收益均等的情况下贪心是更好的选择。通过这个对比你能清楚地看到贪心利用问题的特殊结构收益均等来简化求解而DP则是一种更通用但代价更高的方法。在实际问题中如果能用贪心优先用贪心贪心不行再考虑DP。我在实际教学中的体会是很多初学者觉得贪心太简单了没什么好学的急着去学DP、图论、数据结构。但恰恰是贪心这种看似简单的思想最能锻炼你对问题结构的洞察力。你能不能一眼看出这个问题可以用贪心你能不能严格证明贪心策略的正确性这些能力比记住几个DP转移方程重要得多。把这道摘苹果的题目吃透比刷十道似懂非懂的难题更有价值。后续可以尝试找一些贪心和DP都能解的题目分别用两种方法实现对比它们的思路差异和性能表现这种对比练习对建立算法直觉非常有帮助。