https://codeforces.com/contest/2055/problem/d
题目大意
给出 $n \ (n \le 2 \times 10^5)$ 长的序列 $a_i$，给出 $k, l \ (1 \le k \le l)$。序列满足 $0 \le a_1 \le a_1 \le \cdots \le a_n \le l$。
起初 $x = 0$，当存在某 $x - k < a_i <= x$ 时，$x$ 会立即变换到 $a_i + k$。任意时刻，a_i 可以以每秒 $1$ 个单位的速度向左或向右移动，或者保持不动。问最少需要多少时间使得 $x$ 变成某个 $\ge l$ 的值。
输出时间 $t$ 乘以 $2$ 的结果。可以证明这样的结果总是一个整数。
简要题解
容易想到，答案是可以二分的。因为 $t$ 秒如果可以做到，$t + 1$ 秒大不了前面都保持静止就好了。
然后判断也不是特别难写。对于 $n = 1$ 的情况，我们总是需要先把 $a_0$ 挪到起点这样 $x$ 才能开始向后跳。对于后续的 $a_i$ 我们总是将其移动到尽可能让这一跳更远的位置（更近的位置只会更难到达下一个点，以及限制下一个点可以在的最右的位置，从而只会让下一跳更近），如果中间弹跳断掉了就直接终止掉，然后判断是否可以跳到超过 $l$ 的位置即可。
为什么最多只会有 $0.5$ 的非整数时间被用到？其实只有通过某个 $a_{i+1}$ 去接 $a_i$ 的一跳需要相向而行的时候才会有这种情况。假设此时为整数时间，则 $a_i$ 与 $a_{i+1}$ 的下标为整数，则最后结果必为 $0.5$ 的整数倍。假设此时为 $0.5$ 的奇数倍时间，则显然 $a_i$ 和 $a_{i + 1}$ 应同处于某 $0.5$ 的奇数倍的位置（否则意味着中间出现了原地等待，则他们不是瓶颈，我们总可以将其放在 $0.5$ 被的位置上），则其差的一半仍会是 $0.5$ 的倍数，因此永远不会用到 $0.5$ 以外的值。
坑点：注意二分的上界不是 $l$ 而是 $l + a[0]$。
（这题虽然和 C 题分数体现的很悬殊，但实际上体感难度差距并不是很大。）
复杂度
$T$：$O(n \log l)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, k, tar; cin >> n >> k >> tar;
k *= 2;
tar *= 2;
vector<int> a(n);
for (int& i : a) {
cin >> i;
i *= 2;
}
auto check = [&](int mid) -> bool {
int x = mid - a[0] + k;
for (int i = 1; i < n; i++) {
if (x < a[i] - mid) break;
x = min(x, a[i] + mid) + k;
}
// cerr << " " << mid << ' ' << x << endl;
return x >= tar;
};
int l = a[0], r = tar * 2;
// cerr << l << ' ' << r << endl;
int mid, ans = tar;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Mysterious Crime - Codeforces Round 519 by Botan Investments