唐巧的博客
·
CSPJ 教学思考：贪心算法
💡
原文中文，约4000字，阅读约需10分钟。
📝
内容提要
贪心算法通过选择局部最佳策略解决问题，适用于时间紧迫的比赛。教学中从简单题目入手，逐步增加难度。排序是贪心算法的基础，STL的sort和priority_queue是重要工具。通过部分背包问题和排队接水等具体题目，展示贪心策略的应用与推导过程。
🎯
关键要点
- 贪心算法通过选择局部最佳策略解决问题，适用于时间紧迫的比赛。
- 教学中从简单题目入手，逐步增加难度，让学生理解贪心的概念。
- 贪心算法通常伴随着排序，STL的sort和priority_queue是重要工具。
- sort函数使用快速排序实现，时间复杂度为O(N*log(N))，适合处理大规模数据。
- 部分背包问题是较简单的贪心题，解题思路是按单位重量的价值排序。
- 排队接水问题需要推导贪心策略，通过排序加总时间解决。
- 凌乱的yyy问题有两种贪心思路，分别是按开始时间和结束时间排序。
- 铺设道路问题的贪心策略是填满第一个坑，并考虑后续坑的填补情况。
❓
延伸问答
贪心算法的基本原理是什么？
贪心算法通过选择局部最佳策略来解决问题，如果局部最佳能保证全局最佳，则可以使用该算法。
在教学中如何引导学生理解贪心算法？
教学中从简单题目入手，逐步增加难度，帮助学生理解贪心的概念和应用。
STL中的sort函数在贪心算法中有什么作用？
sort函数用于排序，是贪心算法的基础工具，能够帮助快速解决相关问题。
部分背包问题的解题思路是什么？
部分背包问题的解题思路是按单位重量的价值排序，能放则放，不能放则分割放部分。
排队接水问题的贪心策略是什么？
排队接水问题的贪心策略是将打水时间按从小到大排序，然后加总时间。
铺设道路问题的贪心策略是怎样的？
铺设道路问题的贪心策略是填满第一个坑，并考虑后续坑的填补情况。
➡️
