如何证明CSES 1085数组划分贪心算法？是否需证明所有贪心问题？

一、贪心策略的正确性证明 #

我们要验证的核心结论是：按左到右遍历，尽可能将当前元素加入最后一个未达上限的子集的策略，得到的子集数量是最少的。

用反证法推导如下：
假设存在一种更优的划分方式（子集数量比贪心结果更少），设贪心划分结果为 G = [G₁, G₂, ..., Gₖ]，更优划分结果为 O = [O₁, O₂, ..., Oₘ]，且 m < k。

从左到右对比两个划分的元素分配：

1. 第一个元素必然同时属于 G₁ 和 O₁，没有其他选择。
2. 假设前 t 个元素在两种划分中，G 的前 i 个子集与 O 的前 j 个子集包含的元素完全一致，且 i ≤ j——因为贪心策略会尽可能把元素塞进当前子集，所以不会比最优划分更早开启新子集。
3. 处理下一个元素 x：
   • 如果 O 中把 x 放进了 Oⱼ，说明 Oⱼ 加 x 不超过上限，那贪心的 Gᵢ 也能放下 x（两者元素完全相同，总和一致），此时贪心也会把 x 放进 Gᵢ，继续保持对应关系。
   • 如果 O 中把 x 放进了 Oⱼ₊₁，说明 Oⱼ 已经装不下 x，那贪心的 Gᵢ 肯定也装不下，此时贪心会新建 Gᵢ₊₁，此时 i+1 = j+1，依然满足 i ≤ j 的关系。

持续这个对比过程直到所有元素处理完毕，最终会得出 k ≤ m，这和我们假设的 m < k 矛盾。因此贪心策略得到的子集数量是最少的，算法完全正确。

本质上，这个问题的贪心策略之所以有效，是因为“尽可能填满当前子集”这个局部最优选择，不会破坏后续元素的最优放置——提前填满当前子集，不会导致后续元素需要额外的子集，反而能减少后续开启新子集的可能。

二、同类贪心问题是否需要逐一证明？ #

是的，必须逐个证明。贪心算法的核心逻辑是局部最优能推导出全局最优，但这个性质并不是所有问题都天然成立的，稍有不慎就会出错。

举个典型反例：
找零钱问题中，若硬币面额为 [1, 3, 4]，要凑出6元。贪心策略（每次选最大面额）会得到 4+1+1，共3枚硬币；但实际最优解是 3+3，仅需2枚。这直接说明贪心策略在这个场景下失效。

因此，每个贪心问题都需要单独验证其正确性，不能直接套用其他问题的贪心逻辑。常用的证明方法有三种：

• 反证法：假设存在更优解，通过推导得出矛盾，从而证明贪心解的最优性。
• 交换论证：证明可以通过交换更优解中的元素顺序或归属，将其转化为贪心解，且不会让结果变差。
• 数学归纳法：先证明小规模问题（如n=1）的贪心解是最优的，再推广到所有规模的问题。

内容的提问来源于stack exchange，提问作者ZIWAKORN