2020 多校第五场 D

2020 多校第五场 D

https://ac.nowcoder.com/acm/contest/5670/D

做法就是把题目给的序列头尾相接形成一个环状序列，枚举环状序列的起点，答案就是「序列长度减去 LIS（最大上升子序列）」的最小值。

环状序列应该不难想，LIS 是怎么来的跟着样例 1 走一遍就知道了：

6
2 4 5 1 3 6

现在我们在一个盘面上按照顺时针方向摆放序列上的数字，然后模拟一下样例解释的做法，首先他 invert 了很多次，多少次不重要。

Invert, 5 times, changing the permutation to 6,2,4,5,1,3;

我们可以理解为将盘面任意地旋转。

接下来他 Drop-2 了很多次，同样多少次不重要，反正这么多次下来就计一次数。

Drop-2, 3 times, changing the permutation to 4,5,1,6,2,3;

它原话是 Take out the second highest note and move it to the lowest position，但是这里是一个圆盘，我们可以把盘面当成抽奖转盘，带有一个固定指针的那种。指针指向的数字往顺时针方向挪一位就是一个 Drop-2 了，如下图所示。挪动的时候，其它数字被挤开相应往顺时针挪动。然后重复操作。

把上面三步 Drop-2 合成一步 multi-drop 来理解，你会发现就是把 4、5、1 这三个数当成一个整体往顺时针挪动一位。

如果你把数字 3 作为参照系，你会发现是 4、5、1 绕开 3 顺时针移动一位。如果你把 4、5、1 这个整体作为参照系，你会发现是数字 3 逆时针移动了三位。因为每次 multi-drop 前后都可以随便旋转转盘，可以再进一步理解，multi-drop 就是将某一个数字移动到任意的位置，就像下面的这样。

那么答案就很显然了，求出 LIS 之后，不在最大上升子序列的数，我们每一个数花一个 multi-drop 操作移动到正确的位置就好了。