解释Cat/Egg投掷问题的这个O(n log n)算法

Question

这个问题(为了确定这样一只猫能活下来的最大楼层,你需要抛出多少只猫才能生存下来.实际上相当残忍),O(n ^ 3)复杂度已经得到了答案.这个问题等同于这个Google Code Jam,它应该可以解决N = 2000000000.

似乎O(n ^ 3)解决方案不足以解决它.从查看解决方案页面,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(动态编程).如果你离开infinity(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(作者)!