题解

思路

把耐久度乘二，记 $L_i=2d_i$。若最终保留的相邻三根柱子下标为 $a,i,b$，中间普通柱 $i$ 能留下当且仅当

因此，只要存在一个满足所有三元限制的非空普通柱序列，它就不会被删除，最终状态也一定非空。新增柱子的最近左右邻居若为 $i,j$，它所需的两倍耐久度恰为 $x_j-x_i$，与它在区间内的具体位置无关。

做法

下面给出从完全枚举、二次动态规划到满分数据结构优化的三档递进算法。

算法一：子集穷举

当 $n\le14$ 时，枚举最终保留的原普通柱集合。对每个有序保留序列，先检查它能否单独稳定；再枚举新增柱子插入在哪两个相邻保留柱之间。

设插入间隙左右端点为 $i,j$。除这两个端点外，其他保留柱的左右邻居已经确定，可以直接检查。新增坐标 $y$ 还需满足：若 $i$ 为普通柱，则 $y\le x_{\operatorname{pre}(i)}+L_i$；若 $j$ 为普通柱，则 $y\ge x_{\operatorname{nxt}(j)}-L_j$。该区间与 $[x_i,x_j]$ 有交集时，候选答案为 $(x_j-x_i)/2$。

正确性来自对所有可能最终保留集合和新增柱子所在间隙的完全枚举。

复杂度为 $O(2^n n^2)$，空间复杂度为 $O(n)$。

算法二：二次动态规划

定义 $f_i$ 为：存在一条从左承重柱到 $i$ 的稳定链时，$i$ 右侧下一根柱子允许到达的最右坐标。令 $f_0=+\infty$。若 $j<i$ 是这条链中 $i$ 的前驱，则连接 $j$ 与 $i$ 必须满足 $f_j\ge x_i$，且 $i$ 允许的下一坐标为 $x_j+L_i$。因为坐标递增，只需选择最大的可行 $j$：

对称地从右向左定义 $g_i$，表示 $i$ 左侧上一根柱子允许到达的最左坐标：

其中 $g_{n+1}=-\infty$。

原建筑稳定当且仅当某个 $f_i\ge x_{n+1}$。否则枚举新增柱子的左右邻居 $i<j$。可行条件为

满足条件时更新 $x_j-x_i$。直接扫描转移和点对即可在 $n\le2000$ 时通过。

复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

算法三：线性 DP 与线段树

计算 $f$ 时，候选前驱按下标入栈。坐标 $x_i$ 单调增加，若栈顶的 $f$ 已小于 $x_i$，它以后永远不会再可行，可以永久弹出；未过期的最大下标就是所需前驱。$g$ 可对称计算，两趟均为 $O(n)$。

最后从左到右枚举右邻居 $j$，在线段树中加入所有满足 $f_i\ge x_i$ 的左候选 $i<j$，叶子保存 $f_i$，区间保存最大值。若 $g_j\le x_j$，在线段树中寻找最右的、值至少为 $g_j$ 的下标 $i$。它给出当前最短间隙。每次查询为 $O(\log n)$。

正确性证明

由 $f$ 的定义与转移归纳可知，$f_i$ 精确描述所有从左侧到达 $i$ 的稳定链可容纳的最右后继；$g_i$ 对右侧稳定链同理。对任意 $i<j$，存在新增坐标 $y$ 连接两条链，当且仅当区间

非空，这恰等价于上述三个可行条件。此时新增柱子的左右邻居为 $i,j$，所需两倍耐久度为 $x_j-x_i$。算法枚举每个 $j$ 并选择最大的可行 $i$，所以既不会遗漏可行方案，也为该 $j$ 取得最小间隙；对所有 $j$ 取最小即为全局最优。

复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

实现注意事项

$2d_i$ 与无穷哨兵使用 64 位整数。最优答案的两倍始终是整数，最后除以二输出即可；评测器仍按原题要求使用 $10^{-4}$ 的绝对或相对误差。

复杂度

三档算法的时间复杂度依次为 $O(2^n n^2)$、$O(n^2)$ 与 $O(n\log n)$，空间复杂度依次为 $O(n)$、$O(n)$ 与 $O(n)$。