algorithm - 解释猫/鸡蛋 throw 问题的 O(n log n) 算法

Question

This problem (你需要将多少只猫扔出建筑物才能确定这样一只猫能够生存的最大楼层。实际上相当残酷)，有一个 O(n^3) 复杂度的公认答案。问题等同于这个 Google Code Jam ，对于 N=2000000000 应该是可解的。

看来O(n^3)的解法还不够好解。从看in the solutions page ，jdmetz 的解决方案(#2)似乎是 O(n log n)。我不太了解算法。谁能解释一下？

编辑

Answer 1

最佳解决方案实际上是O(D*B) (使用问题的术语)，但作者注意到对于大多数 D和 B答案将大于 2^32因此 -1可以返回。
所以，他介绍了maxn等于 1100 - 最大值 D和 F对其进行计数是有意义的。
对于 D, B = 10000他马上返回-1。对于 D, B = 100使用下面的递归公式。仅针对某些“角值”，例如 D = 10000, B = 2 , 使用直接公式。 (有关“直接公式”的详细信息，请参阅他的评论)

对于 D, B < maxn ，作者在评论中提供了公式:f(d,b) = f(d-1,b)+f(d-1,b-1)+1 .函数f此处返回您可以使用不超过 d 确定“断点”的最大楼层数尝试且不超过 b鸡蛋。
公式本身应该是不言自明的:无论我们在哪一层扔第一个鸡蛋，都会有两种结果。它可能会损坏，然后我们最多可以检查 f(d-1, b-1)下面的楼层。或者它可以“存活”，然后我们最多可以检查 f(d-1, b)以上楼层。在当前楼层，这就是f(d-1,b)+f(d-1,b-1)+1总计。

现在，它可以很容易地编码为 DP(动态规划)。如果您离开无穷大 ( 2^32) 检查，它会变得非常干净。

    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;
        }
    }

当我们有数组 f[D][B]存储这些结果，找到 D'和 B'是二分查找。 (因为函数 f 由 d 和 b 单调增长)

PS 虽然我在“猫”问题的答案中确实说过有一个更快的解决方案，但这实际上比我想到的更酷:) 感谢您和 sclo(作者)!