椰程信奥 · 教案

课题：CSP复赛专题3 — 贪心（一）｜ 课时：1 课时（45′）｜ 配套课件：《贪心_互动课件.html》（13 页）
教学目标① 口述贪心本质与四步法；② 独立写出优惠券（整 X 减 + 清余数）与平均分配（差价排序）标程；③ 养成「写完贪心先验证、再构造反例」的习惯。
教学重点四步法落地；优惠券的整 X 批量减；平均分配的差价排序与 long long。
教学难点优惠券「逐件减到 0」为何不是最优；贪心策略的交换论证证明。
教学准备互动课件（投屏）、浏览器打开两模拟器；OJ 题包 COUPON / AVG 已导入当堂测评。

教学过程

环节（时间）教师活动学生活动设计意图
① 导入
4′		 第 1、3 页：用“取十张钞票取面值最大”讲清贪心本质；抛出反例「面额 1/3/4 付 6 元，贪心 4+1+1（3 张）不如 3+3（2 张）」，点出「贪心需前提」。 回忆自己“觉得对却 WA”的经历，建立「大胆假设、小心求证」意识。 破除“贪心=照直觉写”的误解，明确本讲要补“证明”。
② 建框架
8′		 第 4 页抛四步法；第 5 页给交换论证三步走；第 6 页题型地图覆盖基础贪心三类 + 结合型。 在草稿纸写下“分解/定策略/求子最优/堆叠”四词，准备套用。 给可复用元流程，并把“证明”降为可操作步骤。
③ 例题1
优惠券
13′		 第 7 页题意与策略（券给最贵）；第 8 页代码走读，圈「整 X 减 + 清余数」并警告“逐件减到 0”的伪贪心；第 9 页开分步用券模拟器走三样例。 看模拟器“走”每张券给最贵商品；回第 8 页逐行对应；在 OJ 写第一版提交。 用可视化把“为何不能逐件清零”讲透，专治贪心最隐蔽的坑。
④ 例题2
平均分配
13′		 第 10 页题意与差价策略（d_i=b_i−c_i 降序）；第 11 页代码走读，强调全用 long long（答案可到 2×10¹⁴）；第 12 页开差价排序分配模拟器逐行高亮。 观察“按差价降序、前 n 给 B”如何选出；在 OJ 写第二版提交；自查是否开了 long long。 把“排序排什么”与“溢出”两个高频坑一次讲清。
⑤ 诊断小结
7′		 第 13 页易错辨析两连（互动判分）+ 当堂检测；收口「贪心三连问」（按什么排序 / 取前几个 / long long 开了吗）。 完成两道选择题判分；下机前默两道标程，各举一个反例。 把课堂结论转为可执行的自检清单，便于考场上复用。

板书设计

贪心四步法：分解 → 定策略 → 求子最优 → 堆叠全局
优惠券：券给最贵；整 X 减 + 清余数（勿逐件清零，会浪费券）
平均分配：d_i=b_i−c_i 降序，前 n 给 B，其余给 C；答案用 long long
证明：交换论证——把最优解的第一步换成贪心选择，总收入不降

检测标准

等级表现
达标能写出两题标程并 AC；能说清优惠券为何用整 X 减、平均分配为何按差价排序。
良好在达标基础上，能用交换论证口述平均分配的正确性，并主动举出贪心反例（如 1/3/4 面额）。
待强化把优惠券写成“逐件减到 0”，或平均分配用 int 溢出——需回看第 8、11 页重做。