一个长度为 n 的初始排列为 [1,2,3,4,…,n] 。
对其进行下列操作:
- 首先,我们将其循环移动 k 位, k 为一个未知数 (0≤k≤n−1) 。
将一个长度为 n 的数组循环移动k位就是将原数组最后 k 位移动到第 1∼k 位,并将其余 n−k 位移动到第 k+1∼n 位。比如说,我们将 [1,2,3,4,5,6] 循环移动两位,就是 [5,6,1,2,3,4] 。
- 然后,我们将数组中任意两个数交换,最多进行 m 次。
给定 n,m 和最后的结果,你需要找出所有可能的 k 值。
3≤n≤3×105,0≤m≤3n,1≤pi≤n ,每个 1∼n 的整数均只出现一次。
首先不难想到枚举每一个 k,求出循环移位之后的排列 a,快速判断能否在 m 次交换内让 p=a。
若我们交换 m 次,最多能让 p 中 2m 个数归位。也就是说,p 中至少要有 n−2m 个数不用交换就已经归位。
因为对于每个 i,不交换就让 pi=ai 的 a 只会有一个,所以每个 i 都只会有一个 k 能让 pi 不交换就已经归位,设这个 k 为 ki。
由于 m≤3n,所以 n−2m≥3n。也就是说,我们枚举的 k=k′ 要满足至少有 3n 个 ki=k,所以满足条件的 k′ 最多只有 3 个。
但是这个条件只是必要条件,不是充分条件,所以我们还要作进一步的判断。设循环移位 k′ 位之后的排列是 a,那么问题就转化为求让 p=a 的最少交换次数。
这是一个经典问题,建立 n 个点,对于每一个 pi,都从 i 向满足 pj=ai 的 j 连一条有向边,最少交换次数即为 n−环个数。
其实也可以从 i 向满足 pj=ai 的 j 连一条无向边,最少交换次数即为 n−连通块个数。
解释:
考虑这样构造出来的图,显然每个点都有且仅有一个入度和一个出度,那么最后的图一定是由若干个环组成的。
考虑一次交换操作,显然只有交换同一个环内的点是有用的,交换 pi,pj 就相当于把 i 的出边和 j 的出边交换,相当于把大环断成两个小环,那么总共需要断 环的大小−1 次,所以做法成立。