贪心算法笔记（C++版）
一句话理解
> 贪心算法：每一步都选当前看起来最优的选择，不管以后会怎样。
就像吃自助餐——每次只拿最贵的菜，最后不一定吃得最爽，但在某些问题上这就是最优解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、什么是贪心算法？
贪心算法：在每一步都做出当前状态下最好的选择，希望通过局部最优达到全局最优。
核心思想：只看眼前，不回头，不后悔。
特点：
* 步骤简单，容易想
* 不一定每次都对（需要证明贪心是正确的）
* 一旦正确，效率很高
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、贪心算法的基本框架
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、经典题目
题目1：活动安排（选最多的活动）
题目描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。同一个时间只能参加一个活动，问最多能参加几个活动。
贪心策略：按结束时间从小到大排序，每次选结束最早的、且不冲突的活动。
输入样例：
输出样例：
为什么按结束时间选是对的？：结束越早，留给后面的时间越多。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目2：排队接水（平均等待时间最小）
题目描述：有 n 个人接水，第 i 个人接水需要 t[i] 分钟。问怎样排队能使所有人的平均等待时间最小？输出总等待时间。
贪心策略：按接水时间从小到大排队。
输入样例：
输出样例：
（等待时间 = 0 + 3 + (3+1) + (3+1+4) + (3+1+4+2) = 0+3+4+8+5=20）
为什么按接水时间排序是对的？：用时短的人先接水，后面的人等得更少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目3：找零钱（用最少硬币）
题目描述：有 1 元、5 元、10 元、20 元、50 元、100 元的硬币无限个。要支付 M 元，问最少需要多少硬币。
贪心策略：先用最大面额的硬币，不够再用小面额。
输入样例：
输出样例：
（100+50+10+5+2+1？不对，这是金额。注意：M=168时：100元1个+50元1个+10元1个+5元1个+1元3个？等等算错了。100+50=150，差18，10元1个=160，差8，5元1个=165，差3，1元3个=168。一共1+1+1+1+3=7个。）
注意：这种贪心在人民币面额下是对的（因为每种面额都是更大面额的约数）。如果不是这种面额（比如1,3,4元，要付6元，贪心会选4+1+1=3个，但最优是3+3=2个），贪心不一定对。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、贪心的正确性
贪心算法不一定总是对的！使用前需要判断：
情况 说明 适用 问题有“贪心选择性质”（局部最优能推出全局最优） 不适用 当前选择会影响后面的选择
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、贪心 VS 其他算法
对比 贪心 动态规划 枚举 思路 每步选最优 考虑所有可能 全部试一遍 时间复杂度 通常 O(n log n) O(n²) 或更高 可能很高 正确性 需要证明 一定正确 一定正确 适用场景 有贪心性质的问题 最优化问题 数据范围小
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、贪心常见题型
题型 贪心策略 活动安排 按结束时间排序 排队问题 按时间排序 区间选点 按右端点排序 删数问题 找第一个下降点删除 找零钱 用最大面额（特定面额下）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、总结
要点 内容 核心思想 每步都选当前最好的 优点 简单、高效 缺点 不一定正确 使用前 证明或确认贪心是正确的 经典应用 活动安排
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
记忆口诀
> 贪心每步选最好，局部最优不烦恼
> 活动安排按结束，排队接水按时长
> 用前必须想清楚，贪心性质要记牢
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
