题意
题目说的很清楚了亚。。把题面再复制一遍吧。
有(N)人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧(T)秒。每个烟花只能被点燃一次。
(1)号站在原点，(i)号((1 leq i leq N))到(1)号的距离为(X_i)。保证(X_1 = 0)，(X_1, X_2, ..., X_N)单调递增（可能有人位置重叠）。
开始时，(K)号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。
求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数。note：所求的速度为全程中最大速度的最小值。
题解
本题满足二分性质，我们可以二分一个所求(v)，然后判断是否有合法方案。
注意到对于一个区间([L, R])，且区间中起初有一个烟花是燃烧的，如果可以点燃区间中所有烟花，其中一种方案一定满足，所有人的相对位置不发生改变。因此，在这种方案中，只要满足(x_L + vT(R - L) geq x_R - vT(R - L))即可。而同样，如果不满足(x_L + vT(R - L) geq x_R - vT(R - L))这个条件，那么显然整个区间是不能被全部点燃的（以(v)的速度）。
观察上面的柿子，移项，得
则令(a_i = x_i - 2vTi)，则问题变为从区间([K, K])开始向外扩展区间，要保证每个时刻扩展出的区间([l, r])要满足(a_l geq a_r)。当且仅当能扩展到区间([1, n])，所有烟花可以被点燃。
观察一个性质：对于可扩展区间([l, r])，对于(i < l)，如果满足：
1.(a_i geq a_l)
2.(forall j in [i, l])，(a_j geq a_r)
则可知区间([i, r])也是可以扩展的。
就这样，我们可以左右不断做这个操作，每次固定合法区间左（右）端点，向外移动右（左）端点。
如果某次向左向右都无法扩展了，且是因为(a_i geq a_l wedge exists j in [i, l], a_j < a_r)这样的原因，那么说明无法点燃整个大区间([1, n])的烟花。
否则，我们会得到一个极大的区间([ml, mr])（这个区间不能通过上述的方式扩展，且是因为( exists i < l, a_i geq a_l)）。
这时，我们只能换一种方式来判断——从整个大区间([1, n])向内缩。
此时，对于可缩区间([l, r])，对于(l < i leq ml)，如果满足：
1.(a_i geq a_l)
2.(forall j in [l, i])，(a_j geq a_r)
区间([i, r])也可以缩得。
直到区间([ml, mr])如果可以缩得，那么就说明可以点燃所有烟花。
证明？其实这是一个逆向过程，把过程逆一下就挺显然的了。（可以画个折线图试试）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, K, T, x[N];
ll a[N];
bool check (int v) {
for (int i = 1; i <= n; ++i) {
a[i] = 0ll + x[i] - 2ll * T * v * i;
}
if (a[1] < a[n]) {
return 0;
}
int ql = K, qr = K, l, r;
for (int i = K - 1; i; --i) {
if (a[i] >= a[ql]) {
ql = i;
}
}
for (int i = K + 1; i <= n; ++i) {
if (a[i] <= a[qr]) {
qr = i;
}
}
for (l = r = K; l != ql || r != qr; ) {
int ok = 0, L = l, R = r;
for ( ; L > ql && a[L - 1] >= a[r]; ) {
if (a[--L] >= a[l]) {
break;
}
}
if (L < l && a[L] >= a[l]) {
ok = 1, l = L;
}
for ( ; R < qr && a[R + 1] <= a[l]; ) {
if (a[++R] <= a[r]) {
break;
}
}
if (R > r && a[R] <= a[r]) {
ok = 1, r = R;
}
if (!ok) {
return 0;
}
}
for (l = 1, r = n; l != ql || r != qr; ) {
int ok = 0, L = l, R = r;
for ( ; L < ql && a[L + 1] >= a[r]; ) {
if (a[++L] >= a[l]) {
break;
}
}
if (L > l && a[L] >= a[l]) {
ok = 1, l = L;
}
for ( ; R > qr && a[R - 1] <= a[l]; ) {
if (a[--R] <= a[r]) {
break;
}
}
if (R < r && a[R] <= a[r]) {
ok = 1, r = R;
}
if (!ok) {
return 0;
}
}
return 1;
}
int main () {
scanf("%d%d%d", &n, &K, &T);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x[i]);
}
int l = 0, r = 1e9, mid, ans = r;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%d
", ans);
return 0;
}