[数据结构与算法]蓝桥杯 2018年第九届 测试次数

这个题目着实让我考虑很久，在慢慢扒开这一题目的解题思路，让我有种心驰神往的激动。

X 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

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

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

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

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

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

错点一

首先，看到这个题目我们一开始的想法 ：二分！

但是，在一次又一次的试错中，突然发现emmm，直接使用二分似乎是这个题目的某一种讨论情况，所以，贸然使用二分是一种错误的坑点

让我们回到这个题目来

分成三种情况来讨论：

第一：如果你只有一个手机，怎么办？？

最好的确定耐摔程度的做法毫无疑问是从第一层慢慢开始一层层摔，摔倒第K层（即摔破位置）那么，最多和最少的次数无疑是K次；

第二：如果你有无限个手机，怎么办？？

那么这时毫无疑问二分法是最快的解法，1000次只需要10次就能确定;

第三：假设你有1024层楼，但是你的手机不够只有7部手机，即2的K次方，要小于楼层数2的M次方，这怎么办？？

显然，此题就是对第三种情况的讨论：

让我们从简单的两部手机100层楼这个特例考虑起，

首先：

我们可以拿出一部手机A，从任意楼层随意丢，

我就先暂时将100层楼分成10份，让A从10楼，20楼，30楼~~~~直到100楼，

那么A丢的次数范围显然是在【1，10】次；

其次：

若A在第60层就裂开了，那么我们将B拿出来，就可以将范围确定在【50，60】层之间，

此时B丢的次数范围显然是在【1，9】次；

那么此时，丢手机的次数总范围是在【7，15】次之间；

此时我们可以列出一个表格

A ： 10 20 30 40 50 60 70 80 90 100

B ：X1，X2，X3，X4，X5，X6，X7，X8，X9；

假如我们每一次都讨论最坏情况，

假设A在第10层碎，B在X9碎，那么只要10次

假设A在第100层碎，B在X9碎，那么需要19次；

那么可以试出错误的次数在

这里是在【10，19】次中间这个范围的，

那么我们可不可以想一个办法，让这十次实验（A分别取10到100的实验）

最坏次数趋近于一个整数呢？？而不是一个范围？？

造成这十次实验，最坏情况摔下次数不同的原因是什么呢？？

其本身是我们将这个1到100的区间均分了，

因为在最坏情况下，B摔的次数是恒定的，能影响的只有A摔的次数

所以为什么我们不尝试一下改变A的取值呢？

比如我取区间为：（让A的取值间隔不均等）,(即A每多扔一下，B就少扔一下）

n ，（n-1），（n-2），（n-3）·······1；

于是，这个条件就可以转化为1+2+3+4+.......n >= 100;

解出来 n>=13.65;

于是，A的取值为

14，13，12，11，10，9，8，7 ，6 ，5 ，4，1；

那么此时，A无论扔到哪一个区间，最坏的情况都是14次就可以将层数试出来；

那么此时，我们的题目描述已经完成了一大半了，这种对于特殊情况的考虑该如何推向一般方法；

就需要我们快乐的动态规划来完成了！！！

下面进入算法分析环节：

假设我们的楼一共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 ,

(注意是在括号外面加1）??? 次测试
k有多种选择，因此 最好的结果为： dp[i][j] = min( max(dp[k-1][j-1], dp[i-k][j]) + 1 )

所以存在最优解，故我们采取最优策略，求子问题的min即可，

而碎或者未碎这种事情会存在最坏情况，

故我们采用最坏情况的值，求子决策的max即可。

最后，附上代码 ！！

（满满的都是浓缩的精华！不负我看了2个多小时的原理解释）

动态规划还是那个动态规划

#include <bits/stdc++.h>
using namespace std;
int n,foor;
int dp[1005][1005]; 
int main(){
	scanf("%d%d",&n,&foor);
	for (int i=1; i<=n; i++){
		for (int j=1; j<=foor; j++){
			dp[i][j] = j;
		}
	}
	for (int i=2; i<=n; i++){
		for (int j=1; j<=1000; j++){
			for (int k=1; k<j; k++){
				dp[i][j] = min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1); 
			}
		}
	}
	printf("%d",dp[n][foor]);
	return 0;
}

?最后，希望我的代码能给你带来帮助！！