P11066 Solution

· · 题解

但 $m = \lfloor \frac{n}{2} \rfloor$ 的过程事实上很有启发性，我们此时令 $n' = n - 1, k = \lfloor \frac{n}{2} \rfloor$，原过程可以分为两个部分： 1. 将 $p_1 \sim p_k$、$p_{k+1} \sim p_{n'}$ 分别排序； 2. 归并 $p_1 \sim p_k$ 和 $p_{k+1} \sim p_{n'}$。 ## Step 1 考虑同时将 $p_{k+1} \sim p_{n'}$ 向右平移 $1$，花费 $\color{red} n'-k$ 次操作。这时右侧全部被清空。 然后我们将 $p_1 \sim p_k$ 移动到 $p_{n'-k+1} \sim p_{n'}$ 的位置，此时需保证 **移动后的部分整体有序**，也即将左侧所有电梯在若干时刻后有序出现在右侧。这花费 $\color{red} k$ 次操作。 随后，时刻向前移动 $1$ 个单位，花费 $\color{red} 1$ 次操作，随后可以类似地将所有右侧的电梯向左平移使得移动后整体有序，再次花费 $\color{red} n'-k$ 次操作。特别地，如果 $2 \mid n'$ 且此时恰好有 $k$ 位置的电梯移动到 $k+1$ 位置，我们还需要再花费 $\color{red} 2\cdot [2 \mid n']$ 次操作将其再向左平移 $1$（随后在下个时刻将其向右平移 $1$）。可以发现，这样处理后就不会存在其它电梯撞机的影响。 随后，时间还需要向前移动 $n'$ 个单位，花费 $\color{red} n'$ 次操作。 总代价 $\color{red} 3n' - k + 1 + 2 \cdot [2 \mid n']$。 ## Step 2 ### A 这个过程相当于归并排序，但 $[1, n'-k]$ 内的电梯 **只需要右移**，而另一个部分的电梯 **只需要左移**。 记位置 $i$ 的电梯最终需要前往位置 $p_i$。令 $t$ 为满足 $p_t \leq t+1$ 的最大下标，记 $b = n' - k$。 如法炮制地，考虑将右侧所有电梯向右平移 $1$，然后左侧所有电梯向右运输到对应位置，再让时间向前移动 $1$ 个单位。 这之后，只有可能 $p_i \leq i+1$ 的位置仍然阻碍右侧的电梯。此时我们不妨在上一步不去移动它们，而在此时将它们向右平移 $1$，类似地在下一个时刻将它们向左平移 $1$。这一部分，时间最多移动 $n+1-b$ 个单位。 总共花费了 $\color{red} (n' - t + 1) + t + (n' - b + t) + (n + 1 - b) = n' + 2m + t + 2$ 次操作，其中 $t_{\max} = b-1 = n-m-1$，故总代价最大为 $\color{red}2n + m - 1$。 ### B 上一个部分事实上有疏漏：若 $t$ 取到 $b$，则在平移位置 $b$ 的电梯到位置 $b+1$ 时，位置 $b+2$ 存在一个电梯，这时操作会出现不合法情况。 然而在 $t=b$ 时，我们所需要复位的排列是极其特殊的，这只需要将第 $b+1$ 台电梯插入 $[1, b]$ 间的某个空隙即可，于是相当于给定区间 $[L, R]$，将区间内的电梯循环右移。 这个子问题是平凡的，下面直接给出操作过程： - 对于 $i$ 从 $n'$ 到 $R$，将电梯从位置 $i$ 移到位置 $i + 1$。 - 对于 $i$ 从 $R - 1$ 到 $L$，将电梯从位置 $i$ 移到位置 $i + 2$。 - 时间前进 $1$。 - 对于 $i$ 从 $L - 1$ 到 $1$，将电梯从位置 $i$ 移到位置 $i + 1$。 - 将电梯从位置 $R + 1$ 移到位置 $L$。 - 时间前进 $1$。 - 对于 $i$ 从 $L$ 到 $2$，将电梯从位置 $i$ 移到位置 $i - 1$。 - 对于 $i$ 从 $L + 2$ 到 $n' + 1$，将电梯从位置 $i$ 移到位置 $i - 1$。 - 时间前进 $R - L$。 总代价为 $\color{red} 2n'+2+R-L$，其最大值在 $L=1, R=b+1$ 时取到，有 $\color{red} 3n'-m+2$。 ## 总代价 对 Step 1 和 Step 2 两情况的最大值求和，可以得到在 $n'$ 为奇数时最大为 $\color{red} 5n'+4$，在 $n'$ 为偶数时最大为 $\color{red} 5n'+5$。恰好契合了 $5(n'+1)$ 的数据限制，因此可以通过。