1884. 鸡蛋掉落-两枚鸡蛋

思路

观察样例的解释可以发现答案后面是一个类似6 5 4 3 2 1这样的递减序列，那我们思考为什么会产生这样的序列。在假定操作次数T相同的情况下，因为如果每次扔鸡蛋会用掉一次次数的话，那么在鸡蛋摔碎的情况下下一次用于验证的次数就会少一个。那我们就自然想到反向验证，在操作次数为T的情况下最多可以验证多高的楼层？

设操作次数为T，那么可确定的楼层数为
$$
T+(T-1)+(T-2)+…+1=\frac{T(T-1)}{2}
$$
设楼层数为N，得到不等式
$$
N\leq\frac{T(T-1)}{2}
$$

$$
解得T≥\frac{\sqrt{8n+1}-1}{2}
$$

解方程即可

时间复杂度：O（1）
Solution
1
2
3
4
5
6
class Solution {
public:
    int twoEggDrop(int n) {
        return (int) ceil(sqrt(n * 8 + 1)) / 2;
    }
};