第一期(三)

题目：机器人跳跃问题

考点：二分

该题目类型会同时收录在相关复习专题，供大家学习

收录

蓝桥杯上岸必背！！！(持续更新中~)

往期回顾

蓝桥杯上岸每日N题第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

冲刺蓝桥杯省一模板大全来啦 ~

蓝桥杯4月8号就要开始了 ~

还没背熟模板的伙伴们背起来

祝大家4月8号蓝桥杯上岸 ~

不清楚蓝桥杯考什么的点点下方

考点秘籍

想背纯享模版的伙伴们点点下方

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

想背注释模版的伙伴们点点下方

蓝桥杯必背第一期

蓝桥杯必背第二期

想看JavaB组填空题的伙伴们点点下方

填空题

考前需要刷大量真题,大家一起相互监督，每日做N题，一起上岸吧 ~

机器人跳跃问题

分析

假设当前的E是满足跳跃整个过程所需的能量时，大于E的能量值必定是满足的。
小于E的能量值是不满足的。
我们在假设的这一过程发现了二段性。
那我们接下来可以用二分去二分去我们需要的最小能量值E。

怎么二分?

先写总体框架

我们一起再来背一下模板

int l=0, r= 1e5
while( l<r){
int mid= l+ r>>1
if( check( mid)) r=mid;
// r有可能等于mid
else l= mid+1;
}

E是我们二分出的0号塔的最少能量值！！！

在确定了二分的总体框架后,我们怎么去实现check()函数？

先计算一下跳向每座塔后的能量值为多少？

从低往高跳所需的能量：E-(h(i+1)-E)=2E-h(i+1)
从高往低跳所需的能量：E-(E-h(i+1))=2E-h(i+1)
我们计算发现跳向每座塔后的能量均为2E-h( i+1)

只要在这一个过程中,我们发现E>= maxh。那么后面跳跃时一定是满足条件的。

为什么?

我们推导一下：

2E-h( i+1)= E+ maxh-h( i+1)
由于maxh是所有h(i+1)的最大值!
所以maxh-h(i+1)>=0
所以2E-h(i+1)= E+maxh-h(i+1)>=E
那么后面我们的E一定是单调递增的!
一定不会单调递减，说明能量值是满足条件的。
我们便可以直接返回剩下的E都不需要枚举计算
如果当前的能量值E是小于0的说明当前的能量值不够用！
分析完后,我们来看一下怎么去实现check()函数

check函数的实现:

check(int e){
for(int i=1; i<=n;i++){
    e=2*e-h[i];
    if(e<0)return false;
    if(e>=1e5)return true;
}
return true;

注意：

此题还有一个关键点：

输入输出的理解

要看清楚题目，起初，机器人在编号为0的建筑处。0号塔是没有能量值的
从1开始才有能量值E，问我们的是最初的位置即0号塔需要多少能量才能走完？
我们在输入能量值的时候需要从数组下标1开始。
那有同学会问check()函数计算E值需不需要从1开始？
check()函数计算E值时下标可以从1开始

为什么？

E为二分出的0号塔的最小能量值，满足题意的2*E-h[i+1]。
相当于给我们0号塔的E,从当前的E减去1~n号塔的能量值。

那从0开始写可不可以？

可以！

for(int i=0;i<n;i++){
    e=2*e-h[i+1];
    if(e<0)return false;
if(e>=1e5)return true;
        }

这样写的话也可以，无非是错开一位去枚举。
不过这样写会比较好理解题意。

不清楚的同学可以手动模拟一遍

ACcode1(check()下标从1开始)

import java.util.*;
public class Main {
    static int N=100010;
    static int n;
    static int h[]=new int[N];

    public static boolean check(int e){
        for(int i=1;i<=n;i++){
             e=2*e-h[i];
             //推公式无论是上升还是下降每座塔的能量值均为此
            if(e<0)return false;
            if(e>=1e5)return true;
        }
        return true;


    }
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
       n=sc.nextInt();
        for(int i=1;i<=n;i++)h[i]=sc.nextInt();
        int l=1,r=(int)1e5;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        System.out.println(l);
    }
}

Accode2(check()下标从0开始)

import java.util.*;
public class Main {
    static int N=100010;
    static int n;
    static int h[]=new int[N];

    public static boolean check(int e){
        for(int i=0;i<n;i++){
             e=2*e-h[i+1];
            if(e<0)return false;
            if(e>=1e5)return true;
        }
        return true;


    }
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
       n=sc.nextInt();
        for(int i=1;i<=n;i++)h[i]=sc.nextInt();
        int l=1,r=(int)1e5;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        System.out.println(l);
    }

}