题意
小Hi想知道,如果他每次都按照一种固定的顺序重排数组,那么最少经过几次重排之后数组会恢复初始的顺序?
具体来讲,给定一个1 - N 的排列 P,小Hi每次重排都是把第 i 个元素放到第 Pi个位置上。例如对于 P = (2, 3, 1),假设初始数组是(1, 2, 3),重排一次之后变为(3, 1, 2),重排两次之后变为(2, 3, 1),重排三次之后变回(1, 2, 3)。
被排数组中的元素可以认为是两两不同的。
思路
先单独考虑一个点,模拟一下就能知道这个点至少需要多少步就能回到初始位置,即形成一个环。如果每个点都模拟一次的话复杂度就是,可以进行一个优化:考虑一个环上面的所有点,它们的移动次数一定是相等的,可以把这个环的所有点标记,下次不再访问,则复杂度变成。
现在已经得到每个点的回到初始位置需要移动的次数了,求所有点移动次数的最小公倍数就是答案!(其实一个环中只考虑一个点也可以!)
AC代码
#include <stdio.h>
#include <string.h>
typedef long long LL;
const int maxn = 100+5;
int p[maxn], vis[maxn];
int cir[maxn], cl;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b) {
return a*b/gcd(a, b);
}
int main() {
int n;
while(scanf("%d", &n) == 1) {
for(int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
}
memset(vis, 0, sizeof(vis));
cl = 0;
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
int x = 0;
int u = i;
do{
vis[u] = 1;
x++;
u = p[u];
}while(u != i);
cir[cl++] = x;
}
//求数组cir的最小公倍数就是答案
int ans = cir[0];
for(int i = 1; i < cl; i++) {
ans = lcm(ans, cir[i]);
}
printf("%d\n", ans);
}
return 0;
}
如有不当之处欢迎指出!