GESP 五级 · GESP 202409 C++ 五级第 19 题

判断题 · 答案 B · 考点：贪心算法

题目

贪心算法通过每一步选择局部最优解，从而一定能获得最优解。

答案：B

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】贪心算法｜最优子结构｜贪心选择性质

本题考查《GESP 算法分析与设计大纲》五级"贪心算法"模块的核心适用条件。命题人专卡"贪心算法万能论"——五级考生最容易把"局部最优"直接等同于"全局最优"，忽略了贪心策略生效的硬性前提。

第 28 题· NOIP 2010 普及组初赛试题 · 答案 num <= 2num < 3num == 2go(LEFT_TO_RIGHT)pos[i] == LEFTLEFT == pos[i]hour[i] + go(RIGHT_TO_LEFT)go(RIGHT_TO_LEFT) + hour[i]pos[i] = LEFT看解析 →
第 28 题· NOIP 2016 普及组初赛试题 · 答案 n-nn+1M[i]<C[j]M[i]<=C[j]count<=Acheck(mid)mid-1看解析 →
第 11 题· CSP 2019 入门级第一轮 · 答案 C看解析 →
第 13 题· CSP 2019 提高级第一轮 · 答案 B看解析 →
第 19 题· CSP 2019 提高级第一轮 · 答案 CDB看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。