青蛙过河

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。

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

观察得到：y单调，即y越大越可能满足来回2x的条件，使用搜索得出y的最小值

跳跃能力为y的时候来回2x次 等价 所以长度为y的区间中石头高度之和大于等于2x，用前缀和数组来处理

发现小于2x的，返回false，代码实现

    int r=l+mid-1;
    if(pre[r]-pre[l-1]<2*x)
    return false;

完整代码

#include <iostream>
using namespace std;

int n,x;
int river[100000],pre[100000];
bool check(int mid)
{
    for(int l=1;l<=n-mid;l++)
    {
        int r=l+mid-1;
        if(pre[r]-pre[l-1]<2*x)
        return false;
    }
    return true;
} 

int main()
{
    cin>>n>>x;
    for(int i=1;i<=n-1;i++)
    {
        cin>>river[i];
        pre[i]=pre[i-1]+river[i];
    }
    int l=1,r=n,ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
          ans=mid,r=mid-1;
          else
          l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}