这个难道不简单？
原题链接：62.篝火晚会
2025-07-06 16:17:00
发布于：重庆
简单
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000+10
int a[MAXN],b[MAXN],circle[MAXN],spin[MAXN];
inline int read()//读入优化 不用写
{
char ch='';
while(!isdigit(ch=getchar()));
int num=ch-'0';
while(isdigit(ch=getchar()))num=num10+ch-'0';
return num;
}
int main()
{
int n;
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();b[i]=read();
}
circle[1]=1;
circle[2]=a[1];//第一个点默认切环点
for(int i=1;i<=n;i++)
{
if(b[a[i]]!=i&&a[a[i]]!=i||a[b[i]]!=i&&b[b[i]]!=i)//判断是否可行,由于是个圈，可逆，所以两次判定
{
printf("-1");
return 0;
}
//if(i>1)
if(a[circle[i]]==circle[i-1])circle[i+1]=b[circle[i]]; //由于你并不知道这两个同学的左右，所以判断一下，免得建环重复一个点
else circle[i+1]=a[circle[i]];
}
int ans=n+10;//最多n-1,n+10没问题了
for(int i=1;i<=n;i++)//这里开始是重点，就是找旋转次数，本蒟蒻一开始一直没理解，找大佬讲了好久才懂，如果旋转次相同，就可以看作与序列匹配，即为不用换位置的个数
{
spin[((i-circle[i]+n))%n];//直接膜就可以，+n把负数改过来，最后移动步数为0~n-1；
ans=min(ans,n-spin[((i-circle[i]+n))%n]);//答案是否需要更新
}
memset(spin,0,sizeof(spin));
memset(circle,0,sizeof(circle));
circle[0]=1;
circle[1]=b[1];
for(int i=1;i<=n;i)
{
if(b[circle[i]]==circle[i-1])circle[i+1]=a[circle[i]];
else circle[i+1]=b[circle[i]];
}
for(int i=1;i<=n;i++)
{
spin[((i-circle[i]+n))%n]++;
ans=min(ans,n-spin[((i-circle[i]+n))%n]);
}
printf("%d",ans);
}
有帮助，赞一个