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