题解：CF1041D Glider

· · 题解

前置知识

你需要了解基础语法、前缀和、二分，并掌握一定的推导能力；本篇题解补充了其他题解模糊不清的要点。

思路讲解

题面比较乱，这里简要概括：某飞行员要跳伞，允许在任何点跳下飞机，从高度 h 开始每秒下降一点、前进一点；同时给出 n 个不相交区间，经过区间时飞行员不会下降，只会前进；我们要求出最远飞行距离。

显然，飞行员从某一区间的左端点开始跳是最优的，那我们不妨枚举每一个区间左端点作为起点的情况，求解后更新答案。

考虑前缀和优化，我们预处理出到达第 i 个区间需要下降的距离，即非区间内的距离；每次求解时，二分查找最后一个能到达的完整区间；计算答案时，先累加起始区间左端点到结束区间右端点的距离，再加上可能的剩余飞行距离（可能飞出找到的区间，但未能到达下一个区间），最后更新最大值。

代码展示

注意计算答案的过程，理清思路再慢慢写，以下代码仅供参考：

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define ld long double
#define endl '\n'

#define int long long

// 快速读入，快速输出，可选 
inline int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {  x = x * 10 + (ch - '0');ch = getchar();}return x * w;}
void write(int x) {static int sta[35];int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);while (top) putchar(sta[--top] + 48); }

int n,h,maxn; // 定义变量 
int l[1000007]; // 左端点 
int r[1000007]; // 右端点 
int s[1000007]; // 前缀和预处理数组 

signed main(){
    n=read(),h=read(); // 读入区间数量和高度 
    for(int i=1;i<=n;i++){
        l[i]=read(),r[i]=read(); // 读入左右端点 
        s[i] = s[i-1]+(l[i]-r[i-1]); // 到达第 i 个区间需要下降的距离，也可以说是非区间内的距离
        // 上一区间的值，加上上一区间到这一区间的下降距离
    }

    for(int i=1;i<=n;i++){ // 枚举每个区间左端点作为起点的情况 
        int j=lower_bound(s+1,s+1+n,h+s[i])-s-1; // 计算最后一个可以到达的完整区间 
        int ans=r[j]-l[i]+(h-s[j]+s[i]); // 当前区间到最后区间的距离，加可能的剩余距离，就是答案 
        maxn = max(maxn,ans); // 更新最大值 
    } 
    cout<<maxn; // 输出最大值 

    return 0; // 这题做完了！ 
}