第8章笔记：贪心算法与交换证明

目标

每次选择都要证明可扩展为全局最优，而不是凭局部直觉。

七课依赖

• 区间调度的最早结束：围绕区间调度的最早结束先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 区间覆盖与端点选择：围绕区间覆盖与端点选择先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Huffman合并与最优前缀码：围绕Huffman合并与最优前缀码先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 最小字典序构造：围绕最小字典序构造先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 排序不等式与配对：围绕排序不等式与配对先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 拟阵贪心入口：围绕拟阵贪心入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 贪心失败的最小反例：围绕贪心失败的最小反例先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
区间调度的最早结束	围绕区间调度的最早结束先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
区间覆盖与端点选择	围绕区间覆盖与端点选择先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Huffman合并与最优前缀码	围绕Huffman合并与最优前缀码先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
最小字典序构造	围绕最小字典序构造先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
排序不等式与配对	围绕排序不等式与配对先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
拟阵贪心入口	围绕拟阵贪心入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
贪心失败的最小反例	围绕贪心失败的最小反例先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	贪心需要交换、领先或拟阵结构证明；换一个目标函数就可能失败。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。