自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:44:58，当前版本为作者最后更新于2023-03-10 20:17:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

咋没人做，气抖冷！

可以发现，原最短路一定是数组里最小的元素 $d$，或 $d+1$，或 $d+2$，不妨枚举原最短路长度 $D$。

难点在于决定哪些为 $D$ 的元素真的在最短路上，每个这样的元素需要吞掉旁边的一个非最短路元素，其它真实在最短路上的元素 $x$ 会吞掉至少 $x-D+1$ 个元素，且可以证明吞掉的元素要么是一个区间，要么至多有一个元素与其它元素的区间距离为 2。因此，只要剩下的未被吞掉元素连续段除以二下取整长度和 $\ge$ 需要的最短路元素个数，就能构造出方案。这里可以用简单的线性 dp 求出连续段除以二下取整长度和的最大值。

最后枚举 $1,n$ 的位置，可以发现要么是最短路元素要么距离为常数，所以是 $O(n)$ 种情况，并合并 dp 值。dp 时需要注意 $1,n$ 位置之间的边界，以及序列两边的边界情况。

根据 dp 值构造方案也是 trivial 的，只需倒推每个最短路元素吞掉了哪些元素，得到必要的大小关系并拓扑排序。综上，本题在 $O(n)$ 时间复杂度内得到解决。