自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 23:03:57，当前版本为作者最后更新于2024-09-16 18:05:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

构造 / 排序

$*3200$，$8.5$。

不讲解 $n = 3$，$m = 2$ 和 $m = \lfloor \frac n2 \rfloor$ 的部分分了。红色字体表示花费的操作次数。

考虑 模仿 Subtask 2 进行操作。

令 $n \gets n - 1$ 表示要排序的电梯个数。再取 $m = \lfloor n / 2\rfloor$，我们把过程分为两个部分：

1. 将 $p_{1\dots m}$、$p_{(m+1)\dots n}$ 分别排序；
2. 归并 $p_{1\dots m}$、$p_{(m+1)\dots n}$。

Step 1

我们将 $p_{(m+1)\dots n}$ 先集体向右平移 $1$（$\color{red}n - m$），随后将 $p_{1\dots m}$ 移动到 $p_{(n - m + 1)\dots n}$（$\color{red}m$），并且 让移动后的部分整体有序。

随后时刻向前移动（$\color{red}1$）。然后将所有向右平移的同理向左平移（$\color{red}n - m$），但是这里可能会出现一些情况，如果 $n$ 是偶数，那么你可能需要将 $m + 1$ 位置的电梯（如果此时已经停靠，即 $m \to m + 1$）先向左移动 $1$，再向右移动 $1$（$\color{red}2[2 \mid n]$），容易证明这不会带来任何撞机影响。

随后你最多需要让时间推移 $n$ 次，这部分的总代价即为 $\color{red}3n - m + 1 + 2[2 \mid n]$。

Step 2

这个时候我们相当于归并排序的过程，这个过程性质最良好的一集就是 $[1, b]$ 的数复位 只需要右移（其中 $b = n - m$），而 $[b + 1, n]$ 的数复位 只需要左移。设位置 $i$ 的数需要到达的位置为 $p_i$。

如法炮制地，我们先将右侧的所有数向右平移 $1$，然后将左侧的所有数直接往右送到对应位置。随后时刻流逝 $1$（$\color{red}n - T + 1$）。

这样之后，只有可能 $p_i \leq i + 1$ 的数依然阻碍右侧的数，所以我们在上一步初始不去平移它们，而在这一个时刻将它们向右平移 $1$（$\color{red}T$），这样就不会在向左的路径上形成阻碍了。于是我们可以把右侧的数直接送到对应位置。再在下一个时刻把它们向左平移 $1$ 即可（$\color{red}n - b + T$）。最坏情况这里需要额外经过 $n + 1 - b$ 个时刻，因此总代价为 $\color{red}3n + T - 2b + 2 = n + 2m + T + 2$，其中 $T_{\max} = b - 1 = n - m - 1$，故总代价最大值为 $\color{red}2n + m - 1$。

Step 2.1

你可能会好奇为什么这个时候 $T_{\max} = b - 1$ 而不是 $T_{\max} = b$。

事实上，$T = b$ 的时候上述做法会出现一个小问题：在这个「所以我们在上一步初始不去平移它们，而在这一个时刻将它们向右平移 $1$」一步时，我们要平移 $b$ 到位置 $b + 1$，然而位置 $b + 2$ 存在一个电梯！这个时候你就会爆炸。

然而若 $T = b$，这个时候左侧的所有 $p_i \in \{i, i + 1\}$，这是极为特殊的，如果我们要复位这样的排列，只需要将第 $b + 1$ 台电梯插入 $[1, b]$ 中的某个空隙即可，那么相当于给定 $[L, R]\ (L < R)$，我们将这个区间里的电梯循环右移。

考虑这个问题我们如何做，下面直接给出过程：

• 对于 $i$ 从 $n$ 到 $R$，指令：将电梯从位置 $i$ 移到位置 $i + 1$。
• 对于 $i$ 从 $R - 1$ 到 $L$，指令：将电梯从位置 $i$ 移到位置 $i + 2$。
• 时间流逝。
• 对于 $i$ 从 $L - 1$ 到 $1$，指令：将电梯从位置 $i$ 移到位置 $i + 1$。
• 将电梯从位置 $R + 1$ 移到位置 $L$。
• 时间流逝。
• 对于 $i$ 从 $L$ 到 $2$，指令：将电梯从位置 $i$ 移到位置 $i - 1$。
• 对于 $i$ 从 $L + 2$ 到 $n + 1$，指令：将电梯从位置 $i$ 移到位置 $i - 1$。
• 时间流逝 $R - L$ 次。

计算总代价，有 $n + 1 + 1 + 1 + L - 1 + n - L + R - L = \color{red}2n + 2 + R - L$，其中我们得到 $R = b + 1$，$L \in [1, b]$，故代价最大值为 $\color{red}2n + b + 2 = 3n - m + 2$。

对上述两件事情求和，最大的总代价和为 $\color{red}3n - m + 1 + 2[2 \mid n] + \max(2n + m - 1, 3n - m + 2) = \begin{cases} 5n + 4, n = 2k + 1\\ 5n + 5, n = 2k + 2\end{cases}$。

然而我们的 $n$ 实际上被减少了 $1$，因此完全可以采用 $o = 5n$ 的限制（恰好卡进去！！！111）。