图论,置换群
本题跟蓝桥杯第七届的交换瓶子本质一样,可以搜Acwing1224交换瓶子,不过好像只有报蓝桥杯辅导课才能看
place数组解释:
place[0]表示a[0]在b数组的位置是第2个(下标从1开始)
place[1]表示a[1]在b数组的位置是第4个
…
根据place数组,将数组a分成两个环路:
由于a[0]=5要放在place[0](第2个位置)上,所以5->1
再根据a[1]=1要放在place[1]=4位置上,所以5->1->2
之后根据a[4]=2要放在place[4]=1位置上,所以5->1->2->5
此时已经构成了一个环路,所以第一个分组是5,1,2
第二个分组的分析一致
#include <iostream>
using namespace std;
const int N=110;
int a[N],b[N],place[N];//place数组记录a数组的元素在b中的位置
bool st[N];//记录每个元素的是否已经被分组
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++){
cin >> b[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
if(a[i]==b[j])place[i]=j;
}
int cnt=0,len=-1;
for(int i=1;i<=n;i++){
if(!st[i]){
cnt++;//当前分组加1
int t=0;//记录分组长度
for(int j=i;!st[j];j=place[j]){//从当前元素开始,一直到遍历回自身停止,这样形成一个环路
st[j]=true;
t++;
}
if(t==1){//如果当前元素所在的环路只有它本身时,根据题意,此时长度为-1,分组个数减1
cnt--;
t=-1;
}
len=max(len,t);
}
}
cout << cnt<<" "<<len;
}