题解

思路

追加 $M$ 个数本身一定需要 $M$ 次操作。

做法

若 $T$ 从头到尾都等于初始的 $S_1$，不需要移动。否则必须先把环移动到一个与 $S_1$ 不同的位置；设沿左右两个方向到这种位置的最短距离为 $d$，第一次换值至少且只需 $d$ 次移动。如果环中根本没有另一种值，则无解。

到达最近的另一种值时，当前位置恰在两种值的边界上。以后每当目标序列的相邻需求发生变化，只需在这个边界两侧移动一步；目标值不变时可以原地继续追加。因此，把 $S_1$ 看作追加前的当前值，统计扫描 $T$ 时发生的换值次数 $c$：若 $c=0$，答案为 $M$；否则答案为 $M+d+c-1$。

复杂度

时间复杂度为 $O(N+M)$，空间复杂度为 $O(1)$。