这解释为O（n log n）的算法的猫/鸡蛋投掷问题 [英] Explain this O(n log n) algorithm for the Cat/Egg Throwing Problem

问题描述

此问题（你有多少猫需要抛出了一个建设在为了确定最大的楼，这样的猫会存活下来。很残忍，其实），与为O（n ^ 3）复杂性的一个公认的答案。这个问题就相当于这个谷歌code果酱，这应该是可解为N = 20亿。

This problem (How many cats you need to throw out of a building in order to determine the maximal floor where such a cat will survive. Quite cruel, actually), has an accepted answer with O(n^3) complexity. The problem is equivalent to this Google Code Jam, which should be solvable for N=2000000000.

这似乎为O（n ^ 3）解决方案不够好，以解决这个问题。 从寻找的解决方案页面，jdmetz的解决方案（ ＃2），似乎是为O（n log n）的。 我不太明白的算法。有人能解释一下吗？

It seems that the O(n^3) solution is not good enough to solve it. From looking in the solutions page, jdmetz's solution (#2) seems to be O(n log n). I don't quite understand the algorithm. Can someone explain it?

修改

推荐答案

顶级的解决方案实际上是 O（D * B）（使用问题的术语），但作者注意到，对于大多数 D 和 B 答案会大于 2 ^ 32 ，从而 1 可以退换。
于是，他介绍了 MAXN 等于1100 - 最大的 D 和 F 为这是有意义的计算。
对于 D，B = 10000 他返回-1的时候了。对于 D，低于B = 100 递推公式。仅适用于某些角点，如 D = 10000，B = 2 ，直接公式。 （看他的关于直接式的细节评论）

The top solution is actually O(D*B) (using problem's terminology), but the author noticed that for most D and B answer would be greater than 2^32 and thus -1 can be returned.
So, he introduces maxn equal to 1100 - the maximum D and F for which it makes sense to count.
For D, B = 10000 he returns -1 right away. For D, B = 100 recursive formula below is used. Only for some 'corner values', like D = 10000, B = 2, the direct formula is used. (see his comments for details about 'direct formula')

有关 D，B＆LT; 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 总和。

For D, B < maxn, author provides formula in the comments: f(d,b) = f(d-1,b)+f(d-1,b-1)+1. Function f here returns the maximum number of floors for which you can determine 'break point' using no more than d attempts and no more than b eggs.
Formula itself should be self-explanatory: no matter at which floor we throw first egg, there're two outcomes. It can break, then we can check up to f(d-1, b-1) floors below. Or it can 'survive', then we can check up to f(d-1, b) floors above. With the current floor, that makes it f(d-1,b)+f(d-1,b-1)+1 total.

现在，它可以很容易codeD作为DP（动态规划）。如果你把无限（ 2 ^ 32 ）检查出来，它得到pretty的清洁。

Now, it can be easily coded as DP (dynamic programming). If you leave infinity (2^32) checks out, it gets pretty clean.

    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 双方单调增长ð和 B ）

When we have array f[D][B] storing those results, finding D' and B' is a binary search. (since function f grows monotonously by both d and b)

PS虽然我也确实讲过，在回答了猫的问题有一个更快的解决方案，这其实是比我脑子里想的:)谢谢你凉爽的 sclo 的（作者）！

PS Although I did say in the answer to the 'cats' problem there's a faster solution, this is actually cooler than what I had in mind :) Thanks to you and sclo (author)!

这篇关于这解释为O（n log n）的算法的猫/鸡蛋投掷问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！