我一直在尝试从 A2OJ 2C 梯子：Fox and Box Accumulation解决这个问题：
Fox Ciel 在她的房间里有n 个盒子。它们具有相同的尺寸和重量，但它们可能具有不同的强度。第i 个盒子在其顶部最多可以容纳x i个盒子（我们将x i称为盒子的强度）。
由于所有盒子的大小都相同，因此夏尔不能在某个盒子的顶部直接放置一个以上的盒子。例如，假设 Ciel 有三个盒子：第一个有强度 2，第二个有强度 1，第三个有强度 1。她不能同时将第二个和第三个盒子直接放在第一个盒子的顶部。但是她可以把第二个盒子直接放在第一个上面，然后第三个盒子直接放在第二个上面。我们将这样的盒子结构称为一堆。
Fox Ciel 想用所有的箱子堆起来。每堆从上到下都会包含一些盒子，在第 i 个盒子的顶部不能有超过x i个 盒子。她需要建造的最少桩数是多少？
输入
第一行包含一个整数n ( 1 ≤ n ≤ 100 )。下一行包含n 个整数x 1 , x 2 , ..., x n (0 ≤ x i ≤ 100)。
输出
输出一个整数——可能的最小堆数。
我有一个贪婪的解决方案，但我无法严格证明它。这就是为什么我需要你们的帮助！
我的算法如下（非常直观）：
对 input_array 进行排序。
初始化一个名为 pile_array 的数组。
从上到下开始建桩，即先从最低强度开始。我选择 input_array 中强度最低的框，然后将其从 input_array 中删除，并将其添加到 pile_array。
然后，在步骤 3 中删除元素后，我从 input_array 中的剩余元素中检查下一个强度最低的块，并查看是否可以将其添加到 pile_array 以形成有效堆。如果可以，就去做。否则继续。（此步骤中选择的元素当然可能具有与添加到 pile_array 中的最后一个元素相同的强度。）
然后我对该元素重复步骤 3，即在 pile_array 中添加元素并从 input_array 中删除它。
在我们无法再填充 pile_array 之后，我将一个已预初始化的计数器增加 1。然后我清除 pile_array（以便我可以重用它）。
对输入数组的所有剩余元素重复此过程。
然后我输出答案作为计数器。
该实现具有 O(n^2) 复杂度。
现在主要问题是：我无法证明我的算法给出了最佳大小的解决方案。我尝试了以下方法：
通过交换证明任何最优解都可以转化为上述构造的贪心解。失败是因为我无法在非贪婪解决方案中获得任何有用的结构......
通过“贪婪总是领先”方法证明：到目前为止，我的主要思想是，任何不完全相同的最优解都小于所有块的最大“强度/容量使用”。但我无法正式化我的论点。
我很想有人给我一个关于算法证明的提示。请帮忙，因为我无法继续我的生活，直到我证明这个问题是因为强迫症:(。
简单评论一下：我刚刚检查了传奇大师游客 (Gennady Korotkevich) 在比赛期间实施了相同的算法。刚才我也实现了上面的算法，得到了Accepted。所以放心，这个算法是正确的。