蓝桥杯真题 18省4-测试次数 x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐

阳光穿透心脏的1/2处 2022-12-11 15:13 68阅读 0赞

## 问题描述 ##

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。  
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。  
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

注意：需要填写的是一个整数，不要填写任何多余内容。  
**输入**

没有输入。  
**输出**

输出一个整数。  
**提示**

把答案放在输出语句中输出，例如C/C++语言可以用printf或cout。  
注意：需要输出的是一个整数，不要输出任何多余内容。

## 思路 ##

容易想到二分思路：不断二分范围，取中点，测验是否会摔坏，然后缩小一半范围，继续尝试，很显然，答案为logN（2为底）但是很显然，二分得出的答案是不对的。  
这就有意思了，我们分析可以得出两种情况：

\*\*情况1）\*\*假设我们第一部手机在i层摔坏了，然后最坏情况还要试多少次？这时我们还剩一部手机，所以只敢一层一层试，最坏情况要试到i-1层，共试了i次。

\*\*情况2）\*\*假设我们第一部手机在i层试了，但是没摔坏，然后最坏情况还要试多少次？（这时发现算情况2时依旧是相似的问题，确定了可以用递归来解。）

\*\*最优解（最小值）\*\*是决策后两种情况的最差情况（最大值），我们的本能感觉应该就是让最差情况好一点，让最好情况差一点，这样比较接近正确答案。比如两部手机，一百层，我们可以在50层摔，没坏，这一次就很赚，我们没摔坏手机还把范围缩小了50层。如果坏了，就比较坑了，我们要从1试到50。虽然可能缩小一半，但是最坏情况次数太多，所以肯定要从某个低于五十的层开始尝试。

**归纳表达式**

假设我们的楼一共n层，我们的i可以取1-n任意值，有很多种可能的决策，我们的最小值设为f（n，k），n代表楼高（范围为1-100或101-200其实都一样），k代表手机数.

我们假设的决策是在第i楼扔

对于情况一，手机少了一部，并且我们确定了范围，一定在第i楼以下，所以手机-1，层数为i-1，这时f（n，k）=f(i-1,k-1).+1

对于情况二，手机没少，并且我们确定了范围，一定在第i楼之上，所以手机数不变，而层数-i层，这时f（n，k）=f(n-i,k).+1

**归纳出**

f（n，k）=min（ max（f(i-1,k-1) ，f(n-i,k) ） i取1-n任意数 ）+1

**简单总结**：怎么确定第一个手机在哪扔？每层都试试，哪层的最坏情况（max）最好（min），就去哪层扔。

**动态规划思路：**  
如何解题，也就是如何写出来代码，我们接着往下。

这个动态规划到底怎么写？

\*\*1.\*\*我们摔手机测试按着运气再差的心态来说是吧！摔3次，恰巧都坏了呢?  
\*\*2.\*\*令dp\[i\]\[j\]为i层j个手机的最多(最优)测试次数。第一摔如何摔？每一层都可以作为第一摔。  
\*\*3.\*\*设第一摔选在了第k层。  
第一摔只能有两种结果：**碎或者不碎**。  
**(1)碎**

如果碎了就让他们碎了都-1,楼层和手机，上面的层不再考虑，只需要在下面的层测试，手机少了一部，即 dp\[k-1\]\[j-1\];  
**(2)不碎**

如果没碎，下面的层不再考虑，只需要在上面的层测试，手机还是那么多，即 dp\[i-k\]\[j\]  
**通过上面的分析:**  
因此，我们得出从k层开始摔，运气最坏需要 max(dp\[k-1\]\[j-1\], dp\[i-k\]\[j\]) + 1 次测试  
k有多种选择，因此 最好的结果为： dp\[i\]\[j\] = min( max(dp\[k-1\]\[j-1\], dp\[i-k\]\[j\]) + 1 )  
**所以存在最优解，故我们采取最优策略，求子问题的min即可，而碎或者未碎这种事情会存在最坏情况，故我们采用最坏情况的值，求子决策的max即可。**  
（思路来自博客。博客中大佬众多，在此抱拳仰望！互相学习！）

代码：

#include <stdio.h>
    #define MAX(a,b) (a>b?a:b)
    #define MIN(a,b) (a<b?a:b)
    int main () 
    { 
    	int dp[1001][4];
    	for (int n = 1; n <=3; n++)//它的手机个数
    		for (int i = 1; i <=1000; i++) //楼层数
    		{ 
    			dp[i][n]=dp[i-1][n]+1;// 当前最优次数[楼层][2]=1+当前最优次数[楼层-1][2];//最坏情况
    			for (int j = 1; j <i&&n>1; j++)
    				dp[i][n]=MIN(dp[i][n],MAX(dp[j-1][n-1], dp[i-j][n])+1);//找最优解
    
    		}
    
    	printf("%d",dp[1000][3]);
    	return 0;
    }