887_鸡蛋掉落
题目
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。 每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。 你的目标是确切地知道 F 的值是多少。 无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
示例 1:
输入:K = 1, N = 2 输出:2 解释: 鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。 否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。 如果它没碎,那么我们肯定知道 F = 2 。 因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
分析
假设鸡蛋从X楼层落下碎了,那么接下来得从0到X-1楼层测试且鸡蛋个数-1,否则从X+1楼层测试剩余的(n-x)层,鸡蛋个数不变。 $f(k, n)$表示剩余k个鸡蛋,还有n层楼等待测试 确定f的最小次数, x表示从第几层楼开始测试 $f(k,n) = min(max{f(k-1,x-1), f(k, n-x)} + 1$, 其中f[k][n]) i=1 则f=N,i=0 则f=0; k = 0则f= 0; 相当于把一楼层从x层一分为2,分别在两座楼上测试,然后取两者较大的次数。x从1到n
代码
|
|
时间复杂度优化
如果我们直接暴力转移求解每个状态的dp值,时间复杂度是为 $O(KN^2)$, 即一共有 $O(KN)$个状态,对于每个状态枚举扔鸡蛋的楼层 X,需要O(N)的时间。这无疑在当前数据范围下是会超出时间限制的,因此我们需要想办法优化枚举的时间复杂度。 我们观察到dp(K,N)是一个关于 NN 的单调递增函数,也就是说在鸡蛋数 KK 固定的情况下,楼层数 N越多,需要的步数一定不会变少。在上述的状态转移方程中,第一项 $T_1(X)=dp(K−1,X−1)$是一个随 XX 的增加而单调递增的函数,第二项$T_2(X)=dp(K,N-X)$是一个随着 XX 的增加而单调递减的函数。
这如何帮助我们来优化这个问题呢?当X增加时,$T_1(X)$单调递增而$T_2(X)$单调递减,我们可以想象在一个直角坐标系中,横坐标为X,纵坐标为$T_1(X)$和$T_2(X)$。当一个函数单调递增而另一个函数单调递减时,我们如何找到一个位置使得它们的最大值最小呢?
如上图所示,如果这两个函数都是连续函数,那么我们只需要找出这两个函数的交点,在交点处就能保证这两个函数的最大值最小。但在本题中,$T_1(X)$和$T_2(X)$都是离散函数,也就是说,X的值只能取1,2,3等等。在这种情况下,我们需要找到最大的满足$T_1(X) < T_2(X)$的$X_0$,以及最小的满足$T_1(X) \ge T_2(X)$的$X_1$,对应到上图中,就是离这两个函数(想象中的)交点左右两侧最近的整数。
我们只需要比较在$X_0$和$X_1$处两个函数的最大值,取一个最小的作为X即可。在数学上,我们可以证明$X_0$和$X_1$相差1,这也是比较显然的,因为它们正好夹住了那个想象中的交点,并且相距尽可能地近。因此我们就可以使用二分查找的方法找$X_0$,再得到$X_1$。
二分查找的写法因人而异,本质上我们就是需要找到最大的满足$T_1(X) < T_2(X)$的$X_0$,根据$X_mid$进行二分边界的调整。在得到了$X_0$之后,我们可以知道$X_1=X_0 + 1$。此时我们只需要比较$max(T_1(X_0), T_2(X_0))$ 和 $max(T_1(X_1), T_2(X_1))$,取较小的那个值作为dp值即可。
这样一来, 对于给定的状态$(K, N)$, 我们只需要$O(logN)$的时间,通过二分查找就能得到最优的那个X,因此时间复杂度从$O(KN^2)$降低至$O(KNlogN)$,可以通过本题。
|
|