1. 贪心算法概述与考研机试定位贪心算法Greedy Algorithm作为五大经典算法思想之一在考研机试中占据着举足轻重的地位。这种当下最优即全局最优的解题思路看似简单直接实则暗藏玄机。我在准备ACM竞赛和辅导考研机试的过程中发现约35%的考生在初次接触贪心问题时会出现想当然的错误这正是因为贪心策略的局部最优性往往具有欺骗性。考研机试中的贪心题目通常具有以下特征问题可以分解为多个阶段如区间选择、任务调度每个阶段都有明确的局部最优选择且这个选择不会影响后续阶段的决策空间。典型的考察方向包括区间问题如区间选点、最大不相交区间、哈夫曼编码、背包问题的分数情形等。根据对历年真题的统计分析区间类问题出现的频率高达42%这也是为什么Acwing等知名算法课程都会将其作为重点讲解内容。关键认知贪心算法不是万能的其适用性必须满足贪心选择性质局部最优能导致全局最优和最优子结构性质问题的最优解包含子问题的最优解。这两个性质往往需要通过严格的数学归纳法来证明。2. 贪心算法核心问题分类与解题框架2.1 区间问题家族区间问题是贪心算法的嫡系部队包含以下几种经典变体区间选点问题问题描述选择最少数量的点使每个区间至少包含一个点贪心策略按右端点排序每次选择当前区间的右端点证明思路该点可以覆盖所有与之相交的区间最大不相交区间问题描述选择最多数量的互不重叠的区间贪心策略同样按右端点排序优先选择结束早的区间代码模板sort(intervals.begin(), intervals.end(), [](auto a, auto b){ return a[1] b[1]; }); int count 0, end INT_MIN; for(auto interval : intervals){ if(interval[0] end){ count; end interval[1]; } }区间分组问题问题描述将区间分成最少组每组内区间互不重叠贪心策略用小根堆维护各组的最右端点2.2 任务调度与分配问题这类问题的共同特点是需要在时间或资源约束下做出最优安排活动安排问题与最大不相交区间本质相同变体考虑每个活动的权重加权区间调度加油站问题问题描述在油量限制下到达终点贪心策略在可及范围内选择油量最多的站点2.3 哈夫曼编码与合并问题通过优先队列实现的高频考点priority_queueint, vectorint, greaterint minHeap; for(int num : nums) minHeap.push(num); while(minHeap.size() 1){ int a minHeap.top(); minHeap.pop(); int b minHeap.top(); minHeap.pop(); res a b; minHeap.push(a b); }3. 贪心算法解题的黄金步骤3.1 问题转化四步法问题分解将原问题分解为多个决策阶段贪心选择确定每个阶段的局部最优选择标准可行性检查验证选择是否满足约束条件解合并将各阶段选择合并为最终解3.2 证明贪心策略的三板斧贪心选择性质证明每一步的贪心选择都包含在某个最优解中最优子结构证明子问题的最优解能构成原问题的最优解数学归纳法从基础情形出发归纳证明整体正确性实战技巧当无法严格证明时可以通过反证法假设存在更优解或极端情形测试如所有元素相同来验证策略的正确性。4. 考研机试高频题型深度剖析4.1 区间问题的变形与组合例题类似Acwing 906. 区间分组 给定N个区间要求将这些区间分成若干组使得每组内部的区间两两之间包括端点没有交集求最小组数。解法按左端点排序用小根堆维护每组的最右端点对于当前区间若其左端点≤堆顶需要新开一组否则可以加入该组并更新堆顶sort(intervals.begin(), intervals.end()); priority_queueint, vectorint, greaterint minHeap; for(auto interval : intervals){ if(!minHeap.empty() interval[0] minHeap.top()){ minHeap.pop(); } minHeap.push(interval[1]); } return minHeap.size();4.2 带权区间调度问题当区间带有权重时贪心策略需要结合动态规划按结束时间排序定义dp[i]前i个区间能获得的最大权重转移方程dp[i] max(dp[i-1], dp[p(i)] w[i])p(i)是最后一个不与i冲突的区间4.3 反悔贪心技巧当标准贪心策略不适用时可以采用先贪心后反悔的策略例题项目收益问题 有n个项目每个项目需要c[i]的成本和d[i]天的工期完成后获得p[i]的利润。初始资金为w最多可以做k个项目如何选择解法将所有项目按成本升序排序维护一个大根堆按利润每次将能承担的项目加入堆中选择堆顶项目执行更新资金重复k次或无法继续5. 备考策略与常见陷阱5.1 考研机试的贪心题特征题目描述中通常包含最多、最少、最优等关键词数据范围较大n≥1e5暗示需要O(nlogn)解法往往需要先排序再处理与数据结构优先队列、并查集等结合考察5.2 必须掌握的模板代码区间合并模板sort(intervals.begin(), intervals.end()); vectorvectorint merged; for(auto interval : intervals){ if(merged.empty() || merged.back()[1] interval[0]){ merged.push_back(interval); }else{ merged.back()[1] max(merged.back()[1], interval[1]); } }优先队列自定义比较auto cmp [](pairint,int a, pairint,int b){ return a.second b.second; // 小根堆 }; priority_queuepairint,int, vectorpairint,int, decltype(cmp) pq(cmp);5.3 调试与验证技巧边界测试空输入单个区间/元素所有区间完全重叠所有区间互不重叠可视化调试 对于区间问题可以画出数轴标记区间位置直观验证算法选择的合理性对拍验证 用小规模数据与暴力解法结果对比确保贪心策略正确性6. 从考研到竞赛贪心算法的进阶之路6.1 经典问题变种实战多机调度问题m台相同机器n个作业如何使最大完成时间最小解法将最长作业分配给最早空闲的机器优先队列船运集装箱问题集装箱重量为w[i]船的最大载重C最少需要多少船解法排序后双指针最重最轻配对6.2 贪心与动态规划的混合应用在某些问题中贪心可以作为DP的优化手段例题跳跃游戏II 给定非负整数数组初始位于第一个下标每个元素表示最大跳跃长度求到末尾的最少跳跃次数。贪心解法int jumps 0, curEnd 0, farthest 0; for(int i 0; i nums.size() - 1; i){ farthest max(farthest, i nums[i]); if(i curEnd){ jumps; curEnd farthest; } } return jumps;6.3 在线算法与贪心策略有些问题要求数据流式到达时立即做出决策如缓存淘汰策略这类在线问题往往需要贪心思路LRU缓存淘汰最久未使用的Interval Scheduling不可预知未来任务时的实时调度在准备考研机试的过程中我建议按照基础模板→经典变形→综合应用的三阶段进行训练。每天保持3-5道贪心题的练习量特别注意那些看似能用贪心但实际上需要DP解决的问题如0-1背包问题。记住贪心算法的精髓不在于记忆模板而在于培养那种发现问题具备贪心性质的直觉——这种直觉需要通过大量实践和错误反思来积累。