抓住循环移位的特点,那么数组a, b相对应位置数值不同,说明他们是一组
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 110;
int a[N], b[N], p[N];
int n;
unordered_map<int, int> h;
int main()
{
cin >> n;
for(int i = 0; i < n; ++ i) cin >> a[i], h[a[i]] = i;
for(int i = 0; i < n; ++ i) cin >> b[i];
memset(p, -1, sizeof p);
int cnt = 0, res = 0, mid = 0; // cnt 记录分组个数, res记录最大长度。
for(int i = 0; i < n; ++ i)
{
if(a[i] != b[i] && p[i] == -1) //分组起点
{
cnt ++; mid = 0;
while(p[i] == -1) //递归查找改分组并标记 p[i] = cnt;
{
int j = h[b[i]];
p[i] = cnt;
i = j;
mid ++;
}
res = max(res, mid);
}
}
if(cnt != 0) cout << cnt << ' ' << res << endl;
else cout << 0 << ' ' << -1 << endl;
return 0;
}