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