应该用dp而不是二分
一个问题拥有重叠子问题和最优子结构才能用动态规划来解决
DP：
假设dp[n][m]表示从n层楼m个手机找到的(在最坏情况下)摔手机不碎的最少判断次数。
假设一个手机从第i层扔下，那么有两种情况：
碎了，下面还有(i-1)层，剩下(m-1)个手机，需要dp[i-1,m-1]次。
没碎，上面还有(n-i)层，剩下m个手机，需要dp[n-i][m]次。(子问题)
有了子问题….那就动态规划：
状态转移方程：dp[n, m] = min{ 1 + max(dp[i - 1, m - 1], dp[n - i, m]) | i = 1..n }
边界: dp[i, 1] = i，dp[1, i] = 11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include<stdio.h>
#include <bits/stdc++.h>
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
int dp[1005][50];
int n,m;
#define INF 0x3f3f3f
using namespace std;
int main()
{
cin>>n>>m；
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
dp[j][i]=INF;//剩j个楼层 i部手机
}
for(int i=1;i<=m;i++){//m个手机 剩1层楼 次数1次
dp[1][i]=1;
}
for(int i=1;i<=n;i++){//剩n个楼层 1部手机 次数n次 从下往上扔
dp[i][1]=i;
}
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
for(int k=2;k<=j;k++){
dp[j][i]= min(dp[j][i] ,1+max(dp[k-1][i-1],dp[j-k][i]));
}
}
}
cout<<dp[n][m];
}
思路
想等价变换
对这个问题，原始问题——【100层楼，最少需要几次测试，才能得到摔碎鸡蛋的楼层】，直接考虑不容易考虑，但是，如果将这个问题进行一种等价的转换，这个问题将会变得非常容易解答。个人认为，这个转换是解决这个问题的核心，这个转换是：
转换问题——【两个鸡蛋，进行k次测试，最多可以测试几层楼】
第一次测试，不能太高也能太矮，必须恰到好处，也就是第一枚鸡蛋如果破碎，剩余k-1次机会能将剩余楼层给测试完。
参考链接
https://blog.csdn.net/nka_kun/article/details/79789511
https://blog.csdn.net/qq_34202873/article/details/79784548
https://blog.csdn.net/qq_41923622/article/details/85038621