【精品计划0】蓝桥杯摔手机

淡淡的烟草味﹌ 2022-04-11 03:14 147阅读 0赞

# 原题描述： #

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。  
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。  
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。

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

为了减少测试次数，从每个厂家抽样3部手机参加测试。  
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？  
请填写这个最多测试次数。

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

答案19

### 文章目的 ###

读完题后，我们追求的不是要写出得数（至少对于本博客是不够的），而是用代码实现方法，并思考是否可以优化。

其实本题的方法是非常多种多样的。非常适合锻炼思维。

我们把问题扩展到n个手机来思考。

手机k个，楼n层，最终结果M次。

### 时空复杂度目录 ###

暴力： O(N!)

DP: O(N\*N\*K) O(N\*K)

压空间： O(N\*N\*K) O(N)

四边形不等式优化 O(N\*N)

换思路： O(K\*M)

最优： O(K\*M) O(N)

**文末有测试，大家可以去直观感受一下各方法运行的效率**

### 二分 ###

容易想到二分思路：不断二分范围，取中点，测验是否会摔坏，然后缩小一半范围，继续尝试，很显然，答案为logN（2为底）

但是，二分得出的答案是不对的。**注意:我们要保证在都手机摔完之前，能确定耐摔指数到底是多少。**

举例：

**我们在500楼摔坏了，在250楼摔，又坏了。接下来，我们只能从1楼开始一层一层试**

**因为如果我们在125层摔坏了，就没有手机可以用，也就是永远都测不出来，而这是不被允许的。**其实我们连测第2层都不敢测，因为在第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），就去哪层扔。

### 写出暴力递归 ###

按照分析出来的表达式，我们可以写出暴力递归：

public static int solution1(int nLevel, int kChess) {
    		if (nLevel == 0) {
    			return 0;
    		}//范围缩小至0
    		if (kChess == 1) {
    			return nLevel;
    		}//每层依次试
    		int min = Integer.MAX_VALUE;//取不影响结果的数
    		for (int i = 1; i != nLevel + 1; i++) {
                          //尝试所有决策，取最优
    			min = Math.min(
    					min,
    					Math.max(Process1(i - 1, kChess - 1),Process1(nLevel - i, kChess)));
    		}
    		return min + 1;//别忘了加上本次
    	}

### 改为动态规划 ###

具体思路如下

[https://blog.csdn.net/hebtu666/article/details/79912328][https_blog.csdn.net_hebtu666_article_details_79912328]

public static int solution2(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[][] dp = new int[nLevel + 1][kChess + 1];
    		for (int i = 1; i != dp.length; i++) {
    			dp[i][1] = i;
    		}
    		for (int i = 1; i != dp.length; i++) {
    			for (int j = 2; j != dp[0].length; j++) {
    				int min = Integer.MAX_VALUE;
    				for (int k = 1; k != i + 1; k++) {
    					min = Math.min(min,
    							Math.max(dp[k - 1][j - 1], dp[i - k][j]));
    				}
    				dp[i][j] = min + 1;
    			}
    		}
    		return dp[nLevel][kChess];
    	}

### 压缩空间 ###

我们发现，对于状态转移方程，只和上一盘排的dp表和左边的dp表有关，所以我们不需要把值全部记录，用两个长度为n的数组不断更新即可（具体对dp压缩空间的思路，也是很重要的，我在其它文章中有提过，在这里就不写了）

public static int solution3(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[] preArr = new int[nLevel + 1];
    		int[] curArr = new int[nLevel + 1];
    		for (int i = 1; i != curArr.length; i++) {
    			curArr[i] = i;
    		}//初始化
    		for (int i = 1; i != kChess; i++) {
                      //先交换
    			int[] tmp = preArr;
    			preArr = curArr;
    			curArr = tmp;
                      //然后打新的一行
    			for (int j = 1; j != curArr.length; j++) {
    				int min = Integer.MAX_VALUE;
    				for (int k = 1; k != j + 1; k++) {
    					min = Math.min(min, Math.max(preArr[k - 1], curArr[j - k]));
    				}
    				curArr[j] = min + 1;
    			}
    		}
    		return curArr[curArr.length - 1];
    	}

### 四边形不等式优化 ###

四边形不等式是一种比较常见的优化动态规划的方法

定义：如果对于任意的a1≤a2<b1≤b2，有m\[a1,b1\]+m\[a2,b2\]≤m\[a1,b2\]+m\[a2,b1\]，那么m\[i,j\]满足[四边形][Link 1]不等式。

**对s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\]的证明：**

设mk\[i,j\]=m\[i,k\]+m\[k,j\]，s\[i,j\]=d

对于任意k<d，有mk\[i,j\]≥md\[i,j\]（这里以m\[i,j\]=min\{m\[i,k\]+m\[k,j\]\}为例,max的类似），接下来只要证明mk\[i+1,j\]≥md\[i+1,j\]，那么只有当s\[i+1,j\]≥s\[i,j\]时才有可能有mk\[i+1,j\]≥md\[i+1,j\]

(mk\[i+1,j\]-md\[i+1,j\])-(mk\[i,j\]-md\[i,j\])

=(mk\[i+1,j\]+md\[i,j\])-(md\[i+1,j\]+mk\[i,j\])

=(m\[i+1,k\]+m\[k,j\]+m\[i,d\]+m\[d,j\])-(m\[i+1,d\]+m\[d,j\]+m\[i,k\]+m\[k,j\])

=(m\[i+1,k\]+m\[i,d\])-(m\[i+1,d\]+m\[i,k\])

∵m满足四边形不等式，∴对于i<i+1≤k<d有m\[i+1,k\]+m\[i,d\]≥m\[i+1,d\]+m\[i,k\]

∴(mk\[i+1,j\]-md\[i+1,j\])≥(mk\[i,j\]-md\[i,j\])≥0

∴s\[i,j\]≤s\[i+1,j\]，同理可证s\[i,j-1\]≤s\[i,j\]

证毕

**通俗来说，**

优化策略1）我们在求k+1手机n层楼时，最后发现，第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n层楼时，第一个手机的策略就不用尝试m层以上的楼了。

优化策略2）我们在求k个手机n层楼时，最后发现，第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n+1层楼时，就不用尝试m层以下的楼了。

public static int solution4(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[][] dp = new int[nLevel + 1][kChess + 1];
    		for (int i = 1; i != dp.length; i++) {
    			dp[i][1] = i;
    		}
    		int[] cands = new int[kChess + 1];
    		for (int i = 1; i != dp[0].length; i++) {
    			dp[1][i] = 1;
    			cands[i] = 1;
    		}
    		for (int i = 2; i < nLevel + 1; i++) {
    			for (int j = kChess; j > 1; j--) {
    				int min = Integer.MAX_VALUE;
    				int minEnum = cands[j];
    				int maxEnum = j == kChess ? i / 2 + 1 : cands[j + 1];
                                  //优化策略
    				for (int k = minEnum; k < maxEnum + 1; k++) {
    					int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
    					if (cur <= min) {
    						min = cur;
    						cands[j] = k;//最优解记录层数
    					}
    				}
    				dp[i][j] = min + 1;
    			}
    		}
    		return dp[nLevel][kChess];
    	}

注：对于四边形不等式的题目，比赛时不需要严格证明

通常的做法是打表出来之后找规律，然后大胆猜测，显然可得。（手动滑稽）

### 换一种思路 ###

有时，最优解并不是优化来的。

当你对着某个题冥思苦想了好久，无论如何也不知道怎么把时间优化到合理范围，可能这个题的最优解就不是这种思路，这时，试着换一种思路思考，可能会有奇效。

（比如训练时一道贪心我死活往dp想，肝了两个小时以后，不主攻这个方向的队友三分钟就有贪心思路了，泪目，**不要把简单问题复杂化**）

我们换一种思路想问题：

原问题：n层楼，k个手机，最多测试次数

反过来看问题：k个手机，扔m次，最多能确定多少层楼？

我们定义dp\[i\]\[j\]：i个手机扔j次能确定的楼数。

分析情况：依旧是看第一部手机在哪层扔的决策，同样，我们的决策首先要保证能确定从1层某一段，而不能出现次数用完了还没确定好的情况。以这个为前提，保证了每次扔的楼层都是最优的，就能求出结果。

**依旧是取最坏情况：min（情况1，情况2）**

情况1）第一个手机碎了，我们就需要用剩下的i-1个手机和j-1次测试次数往下去测，dp\[i-1\]\[j-1\]。那我们能确定的层数是无限的，因为本层以上的无限层楼都不会被摔坏。dp\[i-1\]\[j-1\]+无穷=无穷

情况2）第一个手机没碎，那我们就看i个手机扔j-1次能确定的楼数（向上试）+当前楼高h

归纳表达式，要取最差情况，所以就是只有情况2：dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+h

**那这个h到底是什么呢？取决于我敢从哪层扔。因为次数减了一次，我们还是要考虑i个球和j-1次的最坏情况能确定多少层，我才敢在层数+1的地方扔。（这是重点）**

也就是dp\[i\]\[j-1\]的向上一层：h=dp\[i\]\[j-1\]+1

**总：min（情况1，情况2）=min（无穷，dp\[i-1\]\[j-1\]+dp\[i\]\[j-1\]+1）=dp\[i-1\]\[j-1\]+dp\[i\]\[j-1\]+1**

这是解决k个手机，扔m次，最多能确定多少层楼？

原问题是n层楼，k个手机，最多测试次数。

所以我们在求的过程中，何时能确定的层数大于n，输出扔的次数即可

### 最优解 ###

我们知道完全用二分扔需要logN+1次，这也绝对是手机足够情况下的最优解，我们做的这么多努力都是因为手机不够摔啊。。。。所以当我们的手机足够用二分来摔时，直接求出logN+1即可。

当然，我们求dp需要左边的值和左上的值：

![2018120417550852.png][]

依旧可以压缩空间，从左往右更新，previous记录左上的值。

求自己时也要注意记录，否则更新过后，后面的要用没更新过的值（左上方）就找不到了。

记录之后，求出当前数值，把记录的temp值给了previous即可。

public static int solution5(int nLevel, int kChess) {
    		int bsTimes = log2N(nLevel) + 1;
    		if (kChess >= bsTimes) {
    			return bsTimes;
    		}
    		int[] dp = new int[kChess];
    		int res = 0;
    		while (true) {
    			res++;//压缩空间记得记录次数
    			int previous = 0;
    			for (int i = 0; i < dp.length; i++) {
    				int tmp = dp[i];
    				dp[i] = dp[i] + previous + 1;
    				previous = tmp;
    				if (dp[i] >= nLevel) {
    					return res;
    				}
    			}
    		}
    	}
    
    	public static int log2N(int n) {
    		int res = -1;
    		while (n != 0) {
    			res++;
    			n >>>= 1;
    		}
    		return res;
    	}

本题只是填空题，第一种方法就完全能算出来，就是为了追求最优解，追求思维的锻炼。写下了本文。

# 测试： #

暴力： O(N!)

DP: O(N\*N\*K) O(N\*K)

压空间： O(N\*N\*K) O(N)

四边形不等式优化 O(N\*N)

最优： O(K\*M) O(N)

long start = System.currentTimeMillis();
    		solution1(30, 2);
    		long end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution2(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution3(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution4(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution5(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    /*
    结果：
    cost time: 7043 ms
    cost time: 0 ms
    cost time: 0 ms
    cost time: 0 ms
    cost time: 0 ms
    */

暴力时间实在是太久了，只测一个30，2

后四种方法测的大一些（差点把电脑测炸了，cpu100内存100）：

solution(100000, 10):

solution2 cost time: 202525 ms  
solution3 cost time: 38131 ms  
solution4 cost time: 11295 ms  
solution5 cost time: 0 ms

感受最优解的强大：

solution5(1000 000 000,100):0 ms

solution5(1000 000 000,10):0 ms

最优解永远都是0 ms，我也是服了。。

**对比方法，在时间复杂度相同的条件下，空间复杂度一样会影响时间，因为空间太大的话，申请空间是相当浪费时间的。并且空间太大电脑会炸，所以不要认为空间不重要。**

[https_blog.csdn.net_hebtu666_article_details_79912328]: https://blog.csdn.net/hebtu666/article/details/79912328
[Link 1]: https://baike.baidu.com/item/%E5%9B%9B%E8%BE%B9%E5%BD%A2
[2018120417550852.png]: /images/20220411/846da15f5ac94f9697dc549f636d545d.png