看 deepl 翻译的 pdf 笑了一晚上，Link。

单调性

首先发现答案具有单调性，可以二分求解。

十分容易证明，如果现在的速度是 $x$，那么对于答案大于 $x$ 的情况他们完全可以沿用速度为 $x$ 的方案跑完。

不必要的情况

接下来跟着官方题解手玩输入样例，发现了一下一些情况：

1. 对于一样的场面，似乎只改变 $T$ 也会影响答案的方案。
2. 有些人可能会停下来。
3. 有很多人的烟花在被同时点燃。

但是其实这些情况都是没有必要的，似乎有多人做题的时候被误导了（但是学校模拟赛没有给样例解释导致题目没有看懂）。

情况 $1$

显然会有一种通用的方式，如果这个方式可以满足较小的 $T$ 那么也一定可以满足较大的 $T$。

具体的，让本会熄灭的人拿着烟花在站着就行了。

情况 $2$

显然，停止是不必要的。

具体的，如果我们要停止 $t$ 秒那么我们可以向相反方向前进 $\frac{t}{2}$ 就行了。

因为我们考虑的是相对位置，所以整体一起向一个方向移动移动可是一种思路。

情况 $3$

只考虑 $2$ 个的情况，其他的情况容易拓展。

考虑分情况讨论：

• 如果 $2$ 个人相遇后向同一方向运动，那么显然我们可以让其中 $1$ 个人点火之后一起跑，等第 $1$ 个人熄灭之后再传递给第 $2$ 个人。这样有火的时间就从 $T$ 变成了 $2T$。
• 如果 $2$ 个人相遇之后向相反方向移动，那么我们考虑延迟第 $2$ 个人的点时间。为了不影响相对位置，我们可以让第 $1$ 个人先点火，然后让与第 $2$ 个人有关的人一起与第 $1$ 个人运动，保持相对位置不要变。这样当第 $1$ 个人的火将要熄灭的时候第 $2$ 个人再点燃。

规律

1. 因为情况 $3$，场上最多只有 $1$ 个人的火把被点燃。
2. 没点燃的人不会主动远离已经点燃的人，也就是会主动靠近被点燃的人。
3. 拿着烟花的人应该主动靠近下一个需要被点燃的人，这十分显然。

也就是说如果确定了点燃的顺序，那么点燃的最有方案就是确定的。

所以容易想到 $O(n\times n!\times \log V)$ 的做法，可惜题目没有给分。

可行性优化

如果有 $3$ 个人 $x,y,z$ 顺序排列，那么按照 $x\to z\to y$ 的顺序点火肯定没有按照 $x\to y\to z$ 或者 $z\to y\to x$ 的顺序点火优秀。

因此对于任意时刻，被点燃的火把一定是一个包含 $k$ 的连续区间。

那么我们就只需要讨论两侧的情况就行了，时间复杂度为 $O(n\times 2^n\times \log V)$，这样可以获得 $30$ 分。

最优性优化

因为我们发现点燃的一定是一个包含 $k$ 的连续的区间，那么容易想到将最初的 $[k,k]$ 逐步向外拓展到 $[1,n]$。

假设区间 $[l-1,r]$ 是合法的，那么需要满足一下不等式才能扩展到 $[l,r]$ 。

容易理解一个区间 $[l,r]$ 内的所有人汇聚到 $k$ 的时间为 $\frac{x_l-x_r}{2\times v}$。如果出现了 $l$ 或者 $r$ 距离 $k$ 比较近，提前到达了但是另一侧的点还没有到达，那么所有在 $k$ 点的人可以一起向另一侧运动。

那么如果区间 $[l,r]$ 满足条件可以拓展到 $[l,r+1]$ 的要求就是：

$x_{r+1}-x_l\le (r-l+1)\times T$

其意义就是区间 $[l,r]$ 可以一直燃烧直到 $r+1$ 来到 $k$。

同理，如果区间 $[l,r]$ 满足条件可以拓展到 $[l-1,r]$ 的要求就是：

$x_{r}-x_{l-1}\le (r-l+1)\times T$

考虑维护 $f_{i,j}$ 表示区间 $[i,j]$ 能否被表示，直接 $O(1)$ 转移即可，时间复杂度为 $O(n^2\times \log V)$，可以获得 $50$ 分。

不知道叫什么的优化

按照套路，将上面的不等式移项，把 $l$ 和 $r$ 分开，得到：

$x_{r+1}-2v\times T\times (r+1)\le x_{l}+2v\times T\times l$

那么如果令 $x_i\gets x_i-2v\times T\times i$，就得到如果可以过渡到 $[l,r+1]$ 那么需要满足：

$x_l\ge x_{r+1}$

同理，如果要过度到 $[l-1,r]$ 需要满足：

$x_{l-1}\ge x_r$

那么我们可以转化题意：

初始时 $l=r=k$，始终需要满足 $x_l\le x_r$，每一次操作将 $l\gets l-1$ 或者 $r\gets r+1$，问是是否村子啊一个操作到最后使得 $l=1,r=n$。

如果存在一个 $l'$ 满足 $l'\le l$ 且 $\forall i\in [l',l]\cap\mathbb{N}\mid x_i\ge x_r$，那么显然 $[l',r]$ 也是合法的，对于 $[l,r']$ 也是同理。

令 $L$ 取小于 $k$ 的最大的 $x$ 的位置，$R$ 取大于 $k$ 的最小的 $x$ 的位置，那么我们的贪心在最极限的情况下可以到达 $[L,R]$。

考虑从 $[1,n]$ 向回推，如果可以推到 $[L,R]$ 那么就是合法的，反之如果推不到那么就是不合法的。

时间复杂度为 $O(n\log V)$，可以获得 $100$ 分。

Code

过于的丑陋。