CF1041 D.Glider【二分】

题目链接：codeforces 1041D

题解

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}