我一直在尝试通过A2OJ 2C梯形图解决此问题：Fox and Box Accumulation：

  

Fox Ciel在她的房间里有 n 个盒子。它们的大小和重量相同，但强度可能不同。 i ^th 框的顶部最多可以容纳 x _i 框（我们将其称为 x _i 的强度）。

     

由于所有箱子的大小相同，因此Ciel不能在一个箱子的顶部直接放置多个箱子。例如，假设Ciel有三个盒子：第一个盒子的强度为2，第二个盒子的强度为1，第三个盒子的强度为1。她不能将第二个盒子和第三个盒子同时直接放在第一个盒子的顶部。但是她可以将第二个盒子直接放在第一个盒子的顶部，然后将第三个盒子直接放在第二个盒子的顶部。我们将这种箱子的构造称为一堆。

     

Fox Ciel希望从所有盒子中构造出桩。每堆从上到下将包含一些盒子，并且在 i ^th 顶部最多只能有 x _i 个盒子框。她需要建造的最小桩数是多少？

     

输入

     

第一行包含一个整数 n （ 1≤n≤100 ）。下一行包含 n 个整数 x ₁ ，x ₂ ，...，x _n （ 0≤x _i ≤100）。

     

输出

     

输出一个整数-尽可能少的堆数。

我有一个贪婪的解决方案，但我无法严格证明它。这就是为什么我需要你们的帮助！

我的算法如下（非常直观）：

1. 对input_array进行排序。

2. 初始化一个称为ile_array的数组。

3. 从上至下开始构造桩，即从最低强度开始。我在input_array中选择强度最低的框，然后将其从input_array中删除，然后将其添加到pile_array。

4. 然后在步骤3中删除元素之后，我从input_array的其余元素中检查下一个最低强度的块，并查看是否可以将其添加到pile_array中以形成有效桩。如果可以，请执行此操作。否则继续。 （在此步骤中选择的元素的强度当然可能等于添加到pile_array的最后一个元素的强度。）

5. 然后我对该元素重复步骤3，即将元素添加到ile_array中，然后从input_array中删除它。

6. 在我们无法再填充pile_array之后，我增加了一个已预先初始化为1的计数器。然后清除pile_array（以便可以重复使用）。

7. 对于输入数组的所有其余元素重复此过程。

8. 然后我将答案输出为计数器。

该实现具有O（n ^ 2）复杂度。

现在遇到主要问题：我无法证明我的算法给出了最佳尺寸的解决方案。我尝试了以下方法：

1. 通过交换证明可以将任何最佳解转换为上面构造的贪婪解。失败，因为我无法在非贪婪解决方案中获得任何有用的结构。...

2. 通过“贪婪永远保持领先”方法进行证明：到目前为止，我的主要思想是，任何不完全相同的最佳解决方案都小于所有模块的最大“强度/容量使用率”。但是我无法使我的论证正式化。

我会 爱 ，让某人给我提示该算法的证明。请帮忙，因为在我因强迫症（:)证明这个问题之前，我无法继续生活。

快速评论：我刚刚检查了比赛期间传奇超人游客（Gennady Korotkevich）是否实施了相同的算法。我刚才也实现了上述算法，并获得了接受。所以请放心，此算法是正确的。