codeforces1041D Glider（二分/前缀和/贪心）

题目链接：codeforces 1041D

题目思路：

显然，为了尽可能覆盖多的区间，起点一定是某段区间的左端点，故枚举左端点，二分查找终点，下降的高度用前缀和记录即可。具体参见代码。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, h;
struct Node{
   
    int x1, x2;
}node[N];
int pre[N]; // 记录上一个区间的右端点到当前区间左端点距离
bool check(int start, int end) {
   
    return pre[end] - pre[start] < h; // 如果还可以下降，终点还可以往右
}
int main() {
   
   	cin >> n >> h;
    for (int i = 1; i <= n; i++) {
   
        cin >> node[i].x1 >> node[i].x2;
    }
    pre[1] = 0;
    for (int i = 2; i <= n; i++) {
   
        pre[i] = pre[i-1] + node[i].x1 - node[i-1].x2;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
    // 枚举 1~n 个起点
        ll l = i, r = n, mid;
        while (l < r) {
   
            mid = (l+r+1)>>1;
            if (check(i, mid)) {
   
                l = mid;
            } else {
   
                r = mid - 1;
            }
        }
        ll len = node[l].x2 - node[i].x1;
        ll tmp = h;
        tmp -= pre[l] - pre[i]; // 还可以下降的高度，继续下降可能为负，可以通过左移起点加上这段距离
        len += tmp;
        ans = max(ans, len);
    }
    cout << ans << endl;
}