【每日蓝桥】55、一八年省赛Java组真题“测试次数”

你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：测试次数

x星球的居民脾气不太好，但好在他们生气的时候唯-的异常举动是:摔手机.

各大厂商也就纷纷推出各种耐摔型手机. x星球的质监局规定了手机必须经过耐摔测试，并

且评定出一个耐摔指数来，之后才允许上市流通.

x星球有很多高耸人云的高塔,刚好可以用来做耐摔测试.塔的每-一层高度都是- -样的，与

地球上稍有不同的是，他们的第- -层不是地面，而是相当于我们的2楼.

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7.

特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0.

如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

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

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多

少次才能确定手机的耐摔指数呢?

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

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

解题思路：

本题在求解的时候最重要是的理解其中的“采用最佳策略、在最坏的运气下”这一句话的含义。可能很多小伙伴在看到这个要求的时候最先想到的是使用贪心法来做，或者说是看到在1000个数中找出耐摔指数，就使用二分查找来做，但其实不是。

把上面的这一句话换个方式来说“从其中的某一层扔下，要求从这一层比从其他层扔下测试的次数少，但是要的结果是从这一层扔下后，需要测试最多的情况”，这么说可能还是不理解，但是没关系。

我们先看假如有一部手机进行测试，在n层楼下，那么最坏的情况下需要测试的次数是多少？很显然是n次，也就是每一层都试一次，最后得出耐摔指数。

再来说假如有两部手机进行测试，在n层楼下，我们从第i层扔下进行第一次测试，i是小于等于n的，那么有两种情况，一种是手机坏了，那么再测试肯定是从比第i层矮的楼层，同时也只剩下一部手机了，这个时候就是从i-1层测试一部手机，这个是不是就是上段的情景了呢；另一种情况是手机没坏，那么再测试肯定是从比第i层高的楼层，同时还是只有两部手机，这个时候就是从n-i层测试两部手机，这个是不是就是本段的情景的子情景了呢？所以我们最后得出测试次数最多的那轮测试，作为在第i层楼下测试最坏的测试次数。同时在每一层都计算出来以后，我们再找出这每一层测试次数中最小的那个数据，就表示最优的策略，最后得出耐摔指数。下图是以4层为例的测试图：最左边的1，2，3，4表示测试的楼层。

当有三部手机时的情况其实和有两部手机的情况是一样的。在这里还要规定一个，就是如果有0层，那么无论有多少部手机，都是测试0次，在写程序时我们是要把它作为默认的初始值的。所以解法类似于动态规划法，接下来看程序。

答案源码：

   

    

     

      

     
     

      

       package 一八年省赛真题;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       public 
       class Year2018_Bt4 {
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
	
       static 
       int [] f1 = 
       new 
       int[
       1001];	
       //一部手机时的测试次数
      
     
    

     

      

     
     

      
	
       static 
       int [] f2 = 
       new 
       int[
       1001];	
       //二部手机时的测试次数
      
     
    

     

      

     
     

      
	
       static 
       int [] f3 = 
       new 
       int[
       1001];	
       //三部手机时的测试次数
      
     
    

     

      

     
     

      
	
       public static void main(String[] args) {
      
     
    

     

      

     
     

      

       		f1[
       0] = f2[
       0] = f3[
       0];
      
     
    

     

      

     
     

      
		
       //在只有一步手机的情况下，最坏的运气是有多少层就测试多少次，所以对只有一部手机的数组赋值
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       0; i < 
       1001; i++) {
      
     
    

     

      

     
     

      

       			f1[i] = i;	
       //当有i层时，运气最坏时需要测试i次
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      
		
       //如果有两部手机时，计算相应的测试次数
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       1; i <= 
       1000; i++) {
      
     
    

     

      

     
     

      
			
       int minI = i;
       //先假设在有i层时需要测试i次
      
     
    

     

      

     
     

      
			
       //循环从第一层开始测试，测试到第i层
      
     
    

     

      

     
     

      
			
       for (
       int j = 
       1; j <= i; j++) {
      
     
    

     

      

     
     

      
				
       int hao = 
       1+f2[i-j];	
       //计算从j层扔下，好的情况下，手机数还是两个，需要测试多少次
      
     
    

     

      

     
     

      
				
       int huai = 
       1+f1[j-
       1];	
       //计算从j层扔下，坏的情况下，手机数成一个，需要测试多少次
      
     
    

     

      

     
     

      
				
       int maxJ = Math.max(hao, huai);	
       //找出分别在第一次测试好和坏的情况下，测试的最大次数，表示运气最坏的情况
      
     
    

     

      

     
     

      

       				minI = Math.min(minI, maxJ);	
       //判断出最小的测试次数，表示从j层开始是最优策略
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       			f2[i] = minI;	
       //所以层都测试完之后，得到该层最后的测试数
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      
		
       //如果有三部手机时，计算相应的测试次数
      
     
    

     

      

     
     

      
		
       for (
       int i = 
       1; i <= 
       1000; i++) {
      
     
    

     

      

     
     

      
			
       int minI = i;
       //先假设在有i层时需要测试i次
      
     
    

     

      

     
     

      
			
       //循环从第一层开始测试，测试到第i层
      
     
    

     

      

     
     

      
			
       for (
       int j = 
       1; j <= i; j++) {
      
     
    

     

      

     
     

      
				
       int hao = 
       1+f3[i-j];	
       //计算从j层扔下，好的情况下，手机数还是三个，需要测试多少次
      
     
    

     

      

     
     

      
				
       int huai = 
       1+f2[j-
       1];	
       //计算从j层扔下，坏的情况下，手机数成两个，需要测试多少次
      
     
    

     

      

     
     

      
				
       int maxJ = Math.max(hao, huai);	
       //找出分别在第一次测试好和坏的情况下，测试的最大次数，表示运气最坏的情况
      
     
    

     

      

     
     

      

       				minI = Math.min(minI, maxJ);	
       //判断出最小的测试次数，表示从j层开始是最优策略
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       			f3[i] = minI;	
       //所以层都测试完之后，得到该层最后的测试数
      
     
    

     

      

     
     

      

       		}	
      
     
    

     

      

     
     

      
		
      
     
    

     

      

     
     

      

       		System.out.println(f3[
       1000]);
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       }
      
     
   

输出样例：

 

其中有不足或者改进的地方，还希望小伙伴留言提出，一起学习！

感兴趣的小伙伴可以关注专栏！

灰小猿陪你一起进步！