蓝桥杯2018年第九届真题-耐摔指数

解题思路:

注意事项:

参考代码:

package dotcpp.二分;
//x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
//各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，
// 并且评定出一个耐摔指数来，之后才允许上市流通。
//x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，
// 与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
//如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
//特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
//如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
//为了减少测试次数，从每个厂家抽样3部手机参加测试。
//如果已知了测试塔的高度，并且采用最佳策略，
// 在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
//输入
//输入数据，一个整数n（3<n<10000）,表示测试塔的高度。
//输出
//输出一个整数，表示最多测试多少次。
//样例输入
//例如：
//输入：
//3
//再例如：
//输入：
//7
/*
//建议先参考一下算法设计与分析第2版（屈婉玲）第二章的课后习题2.30
F2[n]含义为两部手机测试n次时可以尝试出的最大楼层数
F3[n]含义为两部手机测试n次时可以尝试出的最大楼层数
思路：首先考虑测试n次能支持的最大层数的关系。
首先考虑只有一部手机的时候，因为只有一部手机所以我们只能从第一层开始，一层一层的往上试i
因此次数与最大层数的关系为：F1(n)=n;
然后我们考虑有两部手机的时候，因为题目说了是运气最差的时候，采取最佳方案所以我们首先从最理想位置（第根号n下取整层）下坠，
举个例子：塔10层，当你在5楼下坠时，裂开了就试1，2，3，4 。没开就2部手机继续试6-10 这样运气不好是5次
但 4 楼下坠 裂开试1，2，3 。没开2部手机继续试5-10 运气不好是4次
两部手机试6-10，共5层楼。5-10，共6层。与F2(n-1)形成递推公式
我们扔第一部手机有两种情况
（1）手机碎了，那你现在就只有一步手机了，那就由和只有一部手机时候一样了，不过此时，你已经扔过一次了所以：
F1(n-1)+1 多尝试一次楼层
（2）手机，没碎，你现在有两部手机，n-1次测试次数 ：
F2(n-1)
总的来看，当你有两部手机的时候。
无论裂开与否，此时最多只要尝试
F2(n)=F2(n-1)+1+F1(n-1)
然后就简单了，当我们有三部手机的时候，你先扔一部，又是有两种可能，所以：
F3(n)=F3(n-1)+F2(n-1)+1
* */
import java.util.Scanner;
public class 耐摔指数 {
   static int f2[]=new int[1000];
   static int f3[]=new int[1000];
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int altitude = scanner.nextInt();
       int i = 0;
       while (f3[i] < altitude) {
           i++;
           f2[i] = f2[i - 1] + i;//这里i本身就++了，所以不用加一了
           f3[i] = f3[i - 1] + f2[i - 1] + 1;
       }
       System.out.println(i);
   }
}