【二分】第十三届蓝桥杯省赛C++ A组《青蛙过河》（C++）

【题目描述】

小青蛙住在一条河边，它想到河对岸的学校去学习。

小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。

不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。

小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。

当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

【输入格式】

输入的第一行包含两个整数 n,x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。

第二行包含 n−1 个非负整数 H1,H2,⋅⋅⋅,Hn−1，其中 Hi>0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi=0 表示这个位置没有石头。

【输出格式】

输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

【数据范围】

对于 30% 的评测用例，n≤100；
对于 60% 的评测用例，n≤1000；
对于所有评测用例，1≤n≤10的5次方,1≤x≤10的9次方,0≤Hi≤10的4次方。

【输入样例】

5 1
1 0 1 0

【输出样例】

4

【样例解释】

由于只有两块高度为 1 的石头，所以往返只能各用一块。

第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。

所以小青蛙最少需要 4 的跳跃能力。

【代码】

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N  = 1e5+10;
typedef long long LL;
LL s[N];
int n,x;
bool check(int m)
{
    for(int i =1;i+m<=n;i++)
        if(s[i+m-1]-s[i-1]<x)   return false;
    return true;
}
int main()
{
    cin>>n>>x;
    for(int i=1;i<n;i++)
    {
        int a;
        scanf("%d",&a);
        s[i]=s[i-1]+a;
    }
    x*=2;
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}