二分解题应用--楼层扔鸡蛋问题

昨天在阅微堂看到了WorldQuant去年的笔试题，其中有一道据作者介绍是经典的扔鸡蛋问题，不过我读不懂题目，于是Google之......简单记录一下我的一些收获。

首先读不懂题目并非我的语文能力的问题，而是作者认为这一问题过于经典，于是省略了很多说明性的文字，贴一下我搜索到的完整的题目描述：

1. 你有2个一摸一样的鸡蛋(所有性质相同)。
2. 有一幢100层的楼。注意即使是一楼和地面也有距离的。
3. 鸡蛋可能很硬也可能很软, 意思是有可能从一楼扔下来就碎了, 也有可能从100楼扔下来还不碎。
4. 你必须,是*必须*搞清楚最高从几楼扔下来鸡蛋是不会碎的。
5. 此过程中你被允许打破这2个鸡蛋。
6. 只准用从楼上扔鸡蛋的方式测试, 不能有任何别的辅助工具和手段。

现在就变成一个数学问题：如果你足够聪明, 需要用最少的扔鸡蛋的次数来达到目的, 你会如何选择楼层。

这一问题可以拓展到n个鸡蛋，比如WorldQuant去年的题目就是3个鸡蛋的。很容易想到利用DP来解决这一问题，可以这么考虑，有i层楼j个鸡蛋，则在第k层楼扔下鸡蛋只有破和不破两种情况，如果破了则问题转化为测定k-1层楼，j-1个鸡蛋所需的最小次数＋1；如果不破则转化为测定i-k层楼，j个鸡蛋所需的最小次数。

用f[i,j]表示有i层楼j个鸡蛋，要测定鸡蛋硬度所需的最坏情况下的最小次数。则可得到状态转移方程：

f[i,j]=min(max(f[k-1,j-1],f[i-k,j])+1);(1<=k<=i<=m,1<=j<=n)，边界条件是f[i,1]=i。这种算法的时间复杂度是O(nm^2)。

昨天在搜索的过程中看到TopLanguage Group有一个讨论帖，鋆邓提出了另一种解法，由于最近看了Matrix67大牛的漫话二分系列文章，感觉非常有启发意义。

用f[n,k]表示n个鸡蛋扔k次最多可以测定的楼层数，n固定时显然k越大可测楼层数越多，f[n,k]是递增的。同样分第k次扔时鸡蛋破和没破两种情况讨论，则可得到递推式：

f[n,k]=f[n-1,k-1]{往下可测楼层数}+1+f[n,k-1]{往上可测楼层数}，边界条件是f[1,k]=k。

要求m层n个鸡蛋的情况下所需的最少次数只需在f[n]中对要求的楼层数进行二分检索求出相应的k值即可，这一算法的时间复杂度是O(nk+logm)，k表示在n种鸡蛋数下，m层楼所需的最小次数的和的平均值。

第二种算法的时间复杂度比第一种快了一个数量级，其精髓之处在于对问题模型进行转化，利用二分来确定最小次数。可以发现二分经常不是作为题目的核心算法，但往往利用二分思想能够构造或转换出一个非常优秀和巧妙的模型，从而使许多最优值问题或判可行性问题解决所需的时间复杂度降低一个数量级。