Glider（前缀和+二分）

题目链接：Glider Gym-101911B

解题分析：下落的高度一定，是h。在没有气流的地方每秒下落1；所以可以转化为经过无气流地带的时间总长为h。

　　　　　那么很显然从一个有气流地带的开始，选择下落，那么问题来了，一个一个去试然后一个一个计算他的路径去维护一个最大值吗？未免太过麻烦，所给数据有

　　　　　那么大。

解题关键：二分+前缀和

二分查找用：lower_bound（）

　　　　　　int x=lower_bound(a, a+n, val)-a;

　　　　　　其中i返回值为数组元素值大于等于val的第一个下标。相应地，如果数组中的所有元素的值都小于val，则返回值为数组最后一个元素下标的下一个下标

具体见代码注释：

/* 所给的数据:气流范围是按顺序给的，方便直接求前缀和*/
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <string>
# include <iomanip>
# include <algorithm>
# include <ctime>
# include <cmath>
# include <climits>
# include <cstdlib>
# include <utility>
# include <bitset>
# include <cctype>
# include <cassert>
# include <set>
# include <map>
# include <deque>
# include <queue>
# include <stack>
# include <vector>
# include <functional>
using namespace std;
 
typedef long long ll;
const int maxn=2e5+50;
const ll mod=1e9+7;
const int eps=1e-8;
const double pi=acos(-1.0);
# define mem(a,x) memset((a),(x),sizeof((a)))
# define gcd(a,b) (__gcd(a, b))
# define lcm(a,b) (a*b/__gcd(a, b))
# define lson l,m,rt<<1
# define rson m+1,r,rt<<1|1
# define lowbit(x)(x&(-x))
 
struct nod
{
    int l, r;
}x[maxn];
 
int a[maxn], b[maxn];//a[i]表示前i个气流带的总长度,b[i]表示前i个无气流带(人的下降区）的总长度。
int main()
{
    int n, h;
    cin>>n>>h;
    for(int i=1; i<=n; i++ )
        cin>>x[i].l>>x[i].r;
    int maxx=-1;
    a[1]=x[1].r-x[1].l;
    b[1]=0;
    for(int i=2; i<=n; i++ )
    {
        a[i] = a[i-1] + x[i].r - x[i].l;
        b[i] = b[i-1] + x[i].l - x[i-1].r;
    }
    b[n+1]=0x3f3f3f3f;
 
    for(int i=1; i<=n; i++ )
    {
        int pos=lower_bound(b+1, b+1+n, b[i]+h)-b;//利用二分查找第一个大于等于b[i]+h的点的位置pos
        maxx = max(maxx, a[pos-1]-a[i-1]);//a[pos-1]-a[i-1]为经过的当我们下降h时经过的上升气流的长度
    }
    cout<<maxx+h<<endl;
    return 0;
}