Drop Eggs

LeetCode LintCode BinarySearch

讲真 这道题看题目都好久看不懂，加上这两天倒时差，脑袋晕下午狂睡，两天了都没搞懂这道题。
这里给的方法是数学方法，分析什么情况下会有minimium drops，但还没有彻底懂……

submit 1:

submit 2:

AC:

resources:

Egg Dropping
This video helps:
Drop Eggs

看了上面那个文章总算有一些懂了，当有n floors, two eggs的时候，我们先假设minimium drops in worst case is X，然后来确定如何扔的best strategy. 可以想到，要满足扔的总次数等于X, 那么第一次必须在X floors扔，这样的话如果这个egg breaks, 那么我们需要让第二个egg从1st floor依次扔到X - 1 floor. 这样的话，总次数就是1 + (X - 1) = X次；如果这个egg did not break, 我们第二次要在X - 1 floor去扔，因为只有这样才能满足扔的总次数等于X. 如果first egg在X - 1 floor breaks，我们需要将second egg从 X+1, X+2, ... , X+(X-1)-1 floor去扔，总的drops数目就是2 + (X + (X - 1) - 1 - (X + 1) + 1) = X.于是我们可以发现，每次扔floors增加了X, X-1, X-2,...,2,1。我们要保证最后扔到了n floors以上，也就是X+X-1+X-2+...+2+1 >= 100. 而要求minimiun drops, 就取等号，这样算出来根据求根公式可以得到X = (sqrt(8n+1)-1) / 2;
求出来的X就是我们假设的在worst case下的minimium drops.