0887. Super Egg Drop ======================================================================================================================== 题目信息 -------- :题号: 0887 :难度: Hard :主题: 状态判定、鸡蛋实验、最坏情况 :原题: `LeetCode 0887 `_ :重点: 临界楼层 f 位于 0 至 n;高于 f 投下会碎、在 f 或以下不会碎,需要在最坏情况下用最少次数确定 f 题目重述 -------- 有一栋 ``n`` 层楼和 ``k`` 个性质相同的鸡蛋。存在未知整数临界楼层 ``f``,满足 ``0 <= f <= n``:从高于 ``f`` 的楼层投下鸡蛋会碎,从第 ``f`` 层或更低楼层投下不会碎。 每次可以选择任意楼层投下一个尚未碎的鸡蛋,并立即得知它是否破碎。未碎的鸡蛋可以继续使用,碎掉的鸡蛋不能再用。需要设计能够针对任意可能的 ``f`` 都准确确定其值的实验过程。请返回最坏情况下所需投掷次数的最小值。 ``1 <= k <= 100``,``1 <= n <= 10^4``。 自建示例 -------- 三个鸡蛋用三次覆盖七层: .. code-block:: text 输入:k = 3, n = 7 输出:3 解释:三次投掷配合三个鸡蛋最多可以区分第 0 至第 7 层共八种临界值,例如先在第 4 层测试,再根据破碎与否分别缩小到下方或上方区间。两次投掷最多只有四种结果序列,无法区分八种可能,因此最少需要 3 次。 只有一个鸡蛋: .. code-block:: text 输入:k = 1, n = 4 输出:4 解释:若从较高楼层开始且鸡蛋破碎,就无法继续判断更低楼层。为了保证确定 f,只能依次从第 1、2、3、4 层向上测试,最坏情况下需要 4 次。