题目描述
给定一个长为 n 的数列 {ai} ,你可以多次进行如下操作:
选定 k 个不同的下标 i1,i2⋯,ik(其中 1≤ij≤n),然后将 ai1 移动到下标 i2 处,将 ai2 移动到下标 i3 处,……,将 aik−1 移动到下标 ik 处,将 aik 移动到下标 i1 处。
换言之,你可以按照如下的顺序轮换元素:i1→i2→⋯→ik→i1。
例如:n=4,{ai}={10,20,30,40},i1=2,i2=3,i3=4 ,则操作完成后的 a 数列变为 {10,40,20,30}。
你的任务是用操作次数最少的方法将整个数列排序成不降的。注意,所有操作中选定下标的个数总和不得超过 s 。如果不存在这样的方法(无解),输出 -1
。
输入格式
第一行,两个整数,n 和 s。
第二行,n 个整数 a1⋯n,表示数列 {ai}。
输出格式
如果无解,仅输出 -1
。
否则,第一行输出一个整数 q(可以为 0 ,参见样例 3 ),表示最少需要进行的操作次数。
接下来 2×q 行描述每次操作。
对于每次操作,先输出一个整数 k 表示此操作选定的下标数量,然后在下一行中输出 k 个整数 i1⋯k。
在操作次数 q 最少的情况下,你可以输出任意一种可行方案。
提示
【样例一解释】
你可以用两次操作 1→4→1 和 2→3→5→2 排序数组,但这样会 WA,因为你的任务是最小化 q ,而最优解的 q=1。
一种可行的方法是 1→4→2→3→5→1,即样例输出。
【样例二解释】
所有操作中选定下标的个数总和的最小值为 4(一种可行的方法是 1→2→1 和 3→4→3),因此无解。
【样例三解释】
数组已经有序,因此不需要进行操作。
补充说明:样例 4 和 5 满足子任务 6 和 7 的限制。
【数据范围】
对于 100% 的数据:1≤n≤2×105,0≤s≤2×105,1≤ai≤109。
子任务编号 |
分数 |
限制 |
1 |
0 |
样例 |
2 |
5 |
n,s≤2且1≤ai≤2 |
3 |
n≤5 |
4 |
1≤ai≤2 |
5 |
10 |
a是个排列,s=2×n |
6 |
a是个排列,n≤103 |
7 |
15 |
a是个排列 |
8 |
s=2×n |
9 |
n≤103 |
10 |
20 |
无特殊限制 |
来源:eJOI2018 Problem F「Cycle Sort」
说明:翻译来自 LOJ