青蛙过河--大致思路

解题思路:

二分 + 前缀和

y: 跳跃

青蛙跳到对岸，应该满足的基本条件是任意相邻的两点距离<=跳跃能力

如果存在相邻的两点距离>跳跃能力，则这两点中间一定存在y区间为空区间

如果任意相邻的两点距离<=跳跃能力，则任意y区间不为空区间

也就是说青蛙跳到对岸，应满足任意y区间都包含石头

进行2x次的往返，也就应满足任意y区间都至少包含2x块石头

注意事项:
参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 100005;

int n,x,a[N],b[N];

// 任意y区间都至少包含2x块石头

int o(int k){

     for(int i=1;i<=n-k;i++){

         if(a[i-1+k]-a[i-1]<2*x)

                  return 0;

    }

     return 1;

}

int main(){

    int i,ans,k,L,R;

    cin>>n>>x;

    for(i=1;i<n;i++){

        cin>>b[i];

        b[i]+=b[i-1];

    }

    // 二分

    L=1; R=n;

    while(L<=R){

        k=(L+R)/2;

        for(i=1;i<n;i++)

            a[i]=b[i];

        if(o(k)){

             ans=k;

             R=k-1;

         }

        else

        L=k+1;

    }

     cout<<ans;

     return 0;

}