cnyz's Blog

• https://www.luogu.com.cn/problem/P6892
• https://codeforces.com/gym/101221/problem/A

牛题！

发现这题是最小，那就很离谱，我们连最小步数是什么都是未知的。

所以考虑先爆搜出 $n$ 较小时的方案，诶这个步数都是 $n$ 蛤。

考虑怎么来证这个东西，设 $d$ 为相邻两个货物的相同对个数，初始时 $d=0$，最后 $d=2\times n-2$。

显然一次操作最多让 $d$ 加上 $2$，但第一次操作只能加上 $1$，所以操作下界为 $1+\lceil\frac{2\times n-3}{2}\rceil=n$ 次。

有了这个前提，考虑接下来如何构造，发现当 $n>3$ 时，最后的序列一定位于 $-1\sim 2\times n-2$ 的位置，考虑将问题归约到小问题。

那么，直接打个表，处理 $n=3,4,5,6,7$ 的问题，其他的大力递归处理。

时间复杂度 $O(n)$。