hiho一下 第167周 数组重排

题目1 : 数组重排

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi想知道，如果他每次都按照一种固定的顺序重排数组，那么最少经过几次重排之后数组会恢复初始的顺序？
具体来讲，给定一个1 - N 的排列 P，小Hi每次重排都是把第 i 个元素放到第 Pi个位置上。例如对于 P = (2, 3, 1)，假设初始数组是(1, 2, 3)，重排一次之后变为(3, 1, 2)，重排两次之后变为(2, 3, 1)，重排三次之后变回(1, 2, 3)。
被排数组中的元素可以认为是两两不同的。

输入

第一行一个整数 N ，代表数组的长度。 (1 ≤ N ≤ 100)
第二行N个整数，代表1 - N 的一个排列 P 。

输出

输出最少重排的次数。

样例输入

3
2 3 1

样例输出

3   

题解

1. 本题是一道比较简单的题目，容易看出每个位置上的数字都有固定的循环节。也就是说我们不用考虑整个数组的循环周期，而只用考虑每个位置自己的循环周期。
2. 对于每一个位置，显然循环周期不超过N，所以我们可以O(N)的时间求出一个位置的循环周期、O(N^2)求出所有N个位置的循环周期。
3. 最后对这N个周期求最小公倍数，即是整个数组的循环周期。
4. BTW，以上的算法复杂度是O(N^2)的，在时限内通过本题没有问题。但是你能想办法优化到O(N)吗？
   PS：BTW

Code-1:模拟、暴力

#include <iostream>
using namespace std;

bool judge(int arr[], int N) {
    for(int i = 1; i <= N; i++) {
        if(arr[i] != i) {
            return false;
        }
    }
    return true;
}

int main()
{
    int N, P[105], arr[105], brr[105];
    cin >> N;
    int start = 1;
    bool flag = true;
    for(int i = 1; i <= N; i++) {
        cin >> P[i];
        if(P[i] != i) flag = false;
        arr[i] = brr[i] = i;
    }
    if(flag) {
        cout << 0 << endl;
        return 0;
    }
    int cnt = 0;
    do {
        for(int i = 1; i <= N; i++) {
            brr[P[i]] = arr[i];
        }
        for(int i = 1; i <= N; i++) {
            arr[i] = brr[i];
        }
        cnt++;
    } while(!judge(arr, N));
    cout << cnt << endl;
    return 0;
}

Code-2:循环节、循环周期

#include <iostream>
#include <cstring>
using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int N, P[105], arr[105];
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> P[i];
        arr[i] = i;
    }
    int cnt[105];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= N; i++) {
        int tmp = P[i];
        cnt[i]++;
        while(tmp != i) {
            cnt[i]++;
            tmp = P[tmp];
        }
//        cout << cnt[i] << endl;
    }
    int lcm = cnt[1];
    for(int i = 2; i <= N; i++) {
        lcm = lcm / gcd(lcm, cnt[i]) * cnt[i];
    }
    if(lcm == 1) lcm = 0;
    cout << lcm << endl;
    return 0;
}