示范校建设平台网站,php网站伪静态,网络违法犯罪网站举报,晋中市两学一做网站887. 鸡蛋掉落
给你 k 枚相同的鸡蛋#xff0c;并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f #xff0c;满足 0 f n #xff0c;任何从 高于 f 的楼层落下的鸡蛋都会碎#xff0c;从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次…887. 鸡蛋掉落
给你 k 枚相同的鸡蛋并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f 满足 0 f n 任何从 高于 f 的楼层落下的鸡蛋都会碎从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下满足 1 x n。如果鸡蛋碎了你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少
示例 1输入k 1, n 2
输出2
解释
鸡蛋从 1 楼掉落。如果它碎了肯定能得出 f 0 。
否则鸡蛋从 2 楼掉落。如果它碎了肯定能得出 f 1 。
如果它没碎那么肯定能得出 f 2 。
因此在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2输入k 2, n 6
输出3
示例 3输入k 3, n 14
输出4
解题思路
使用dp二分
n*100k 编号每一种n和k的情况。状态转移方程为当x为不同楼层时dp[k][n]1max(dp[k-1][x-1],dp[k][n-x]),在鸡蛋在楼层x摔坏以后排查下面x-1层和鸡蛋没有摔坏向上排查n-x层取最坏情况的操作次数我们发现当x递增的时候操作次数也会不断减少因此 dp[k-1][x-1],dp[k][n-x]是具有相反的单调性的而我们又必须取二者最坏情况所以我们可以二分查找x尽量找出dp[k-1][x-1],dp[k][n-x]最接近的x就是可取地的最小操作次数
代码
class Solution {MapInteger,Integer mapnew HashMap();public int superEggDrop(int k, int n) {int curn*100k;if(n0)return 0;if(k1)return n;if(map.containsKey(cur))return map.get(cur);int l1,rn,resInteger.MAX_VALUE;while(lr){int mid(r-l)/2l;int lvsuperEggDrop(k-1,mid-1),rvsuperEggDrop(k,n-mid);if(lvrv){rmid-1;resMath.min(1lv,res);}else {lmid1;resMath.min(1rv,res);}}map.put(cur,res);return map.get(cur);}
}
