题解

题意重述：$N$ 个人位于数轴坐标 $X_1\le X_2\le\dots\le X_N$，其中 $X_1=0$。每人有一根可燃烧 $T$ 秒的烟花，仅能被点燃一次。开始时第 $K$ 人刚被点燃，其他人未点燃。任意时刻，任意人奔跑速度不超过某个非负整数 $v$，两人相遇（坐标重合）即可瞬时点燃未点燃者。求最小的 $v$ 使得最终能点燃所有人（允许有人在全部点燃完成前已经熄灭）。

二分答案：显然 $v$ 越大越容易可行，故对 $v$ 做二分查找。关键在于给定 $v$ 的可行性检查。

化简为跨越相邻空隙的“代价”：在速度上界为 $v$ 时，让两侧相向奔跑在最优策略下跨越相邻两人的间距 $\Delta_i=X_{i+1}-X_i$ 所需的“时间消耗”为

点燃某个间隔另一侧的人之后，被点燃者立刻拥有一根新的烟花可继续“输送火力”，等价于得到一笔时长为 $T$ 的“补给”。于是从起点 $K$ 向两侧扩张，穿越每个空隙 $a_i$ 需要支付时间，但抵达一个新的人就获得 $+T$ 的补给。

贪心可行性检查（双端扩展，两阶段）：

• 记从 $K$ 向右的空隙序列为 $a_1,\dots,a_{r}$，向左为 $b_1,\dots,b_{l}$，检查从当前“剩余可用时间” $cur=T$ 出发，能否以某种交替顺序吃掉全部空隙；每吃掉一个空隙 $x$，检查 $cur\gets cur-x$ 不得为负，随后抵达新的人并得到补给 $cur\gets cur+T$。
• 第一阶段尽可能正向推进：在两侧序列上选择一段前缀，使得每一步都不把 $cur$ 压成负数，且累计净收益 $\sum (T-x)$ 尽可能非负，从而把“容易的”空隙尽量吃掉并累计更多冗余时间。
• 剩余未吃掉的空隙若直接相加仍使 $cur<0$，则不可行。否则将两侧剩余段反转，进入第二阶段（反向校验），以相反的顺序再次尝试推进：这相当于验证另一端“最紧的先决约束”也能被满足，避免某处被局部顺序卡死。
• 若两阶段均能完成所有空隙，判为可行；否则不可行。

实现细节：代码中将向右、向左的空隙分别构造成数组 $a,b$，元素为 $\Delta/2v$ 的浮点数；用两个指针和函数 extend/extend2 在两侧来回推进前缀，维护 $cur$ 与累计净收益，最后进行反转与二次检查。二分 $v$ 的最小可行值即为答案。

复杂度：每次检查线性 $O(N)$，二分 $\log V$（$V\le 10^9$），总复杂度 $O(N\log V)$，空间 $O(N)$。

#include <bits/stdc++.h>
#define rep1(i, l, r) for (int i = l; i <= int(r); ++i)
#define rep2(i, l, r) for (int i = l; i >= int(r); --i)
#define rer(i, l, r, a) rep1(i, l, r) read(a[i])
#define ptc putchar
#define il inline
#define eb emplace_back
#define ef emplace_front
#define mp make_pair
#define fst first
#define snd second
#define sqr(x) ((x) * (x))
#define ls(x) x << 1
#define rs(x) x << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 bll;
// typedef unsigned __int128 ubll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10, LOGN = log2(MAXN) + 1, inf = ~0U >> 2, INF = ~0U >> 1;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
namespace stupid_lrc {
    template <typename T> il bool read(T &x) {
        x = 0; bool f = false; char ch;
        while (!isdigit(ch = getchar())) {
            f ^= !(ch ^ '-');
            if (ch == EOF) return false;
        }
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
        if (f) x = ~x + 1; return true;
    }
    il int read() {int x; read(x); return x;}

    template <typename T> il bool read(pair <T, T> &x) {return read(x.fst) && read(x.snd);}

    template <typename T> il void gmin(T &x, T y) {x = x < y ? x : y;}

    template <typename T> il void gmax(T &x, T y) {x = x > y ? x : y;}

    template <typename T, typename ...L>
    il bool read(T &x, L &...y) {return read(x) && read(y...);}

    template <typename T> il T lowbit(const T &x) {return x & -x;}
}
using namespace stupid_lrc;
int n, k, T, x[MAXN];
double a[MAXN], b[MAXN];

il int extend(double *now, int l, int r, double &sum, double pre) {
    if (l > r) return -1;
    sum = 0;
    rep1(i, l, r) {
        if ((pre -= now[i]) < 0) return -1;
        pre += T;
        if ((sum += T - now[i]) >= 0) return i;
    } return -1;
}

il int extend2(double *now, int l, int r, double &sum, double pre) {
    if (l > r) return -1;
    sum = 0;
    rep1(i, l, r) {
        if ((pre -= T) < 0) return -1;
        pre += now[i];
        if ((sum -= T - now[i]) >= 0) return i;
    } return -1;
}

il bool check(int v) {
    int lena = 0, lenb = 0;
    rep1(i, k, n - 1) a[++lena] = (x[i + 1] - x[i]) / 2. / v;
    rep2(i, k, 2) b[++lenb] = (x[i] - x[i - 1]) / 2. / v;
    // cout << lena << ' ' << lenb << endl;
    // rep1(i, 1, lena) cout << a[i] << ' '; puts("");
    // rep1(i, 1, lenb) cout << b[i] << ' '; puts("");
    int l = 1, r = 1; double cur = T;
    // double sum;
    // cout << "?%#" << extend(a, l, lena, sum, cur) << endl;
    while (l <= lena || r <= lenb) {
        double sum = 0; int to;
        if (~(to = extend(a, l, lena, sum, cur))) l = to + 1, cur += sum;
        else if (~(to = extend(b, r, lenb, sum, cur))) r = to + 1, cur += sum;
        else break;
    }
    rep1(i, l, lena) cur += T - a[i];
    rep1(i, r, lenb) cur += T - b[i];
    if (cur < 0) return false;
    // cout << "?" << l << ' ' << r << ' ' << cur << endl;
    reverse(a + l, a + lena + 1); reverse(b + r, b + lenb + 1);
    while (l <= lena || r <= lenb) {
        double sum = 0; int to;
        if (~(to = extend2(a, l, lena, sum, cur))) l = to + 1, cur += sum;
        else if (~(to = extend2(b, r, lenb, sum, cur))) r = to + 1, cur += sum;
        else return false;
    } return true;
}

int main() {
    read(n, k, T); rer(i, 1, n, x);
    if (!x[n]) return puts("0"), 0;
    int l = 0, r = 1e9;
    while (l ^ r) {
        int mid = l + r >> 1;
        check(mid) ? r = mid : l = mid + 1;
    } printf("%d\n", l);
    return 0;
}