AcWing 1921. 重新排列奶牛
原题链接
简单
作者:
ChaseAug_0
,
2022-04-21 23:54:09
,
所有人可见
,
阅读 234
记录每个位置状态,找到下一个没有被使用过的位置
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N], b[N], pos[N];;
bool st[N];
int check(int i)
{
int len = 0;
int p = pos[a[i]];
int x = a[p]; // x = a[pos[a[i]]]: 表示a[i]在b数组中的位置,再把此位置上a数组的值保存下来
while (!st[p])
{
st[p] = true;
len ++;
p = pos[x];
x = a[p];
}
return len;
}
int main()
{
memset (st, false, sizeof(st));
int n;
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++)
{
cin >> b[i];
pos[b[i]] = i;
}
int ans = 0, len = 0;
for (int i = 1; i <= n; i ++)
{
if (a[i] != b[i] && !st[i])
{
ans ++;
len = max(len, check(i));
}
}
if (ans == 0)
{
cout << ans << ' ' << -1 << endl;
}
else cout << ans << ' ' << len;
return 0;
}