代码
2023-01-13 16:32:07
发布于：山东
94阅读
0回复
0点赞
数组范围不让贴1e7啊
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+10;
int arr[N],x[N],y[N],f[N],n,ans=(1<<30);
inline int read()
{
char c=getchar();
int x=0,s=1;
while(c<'0' or c>'9')
{
if(c=='-')
{
s=-1;
}
c=getchar();
}
while(c>='0' and c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*s;
}
void write(int x)
{
if(x<0)
{
putchar('-'),x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
return;
}
signed main()
{
n=read();
for(register int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
for(register int i=1;i<=n;i++)
{
if(x[x[i]]!=i and y[x[i]]!=i or x[y[i]]!=i and y[y[i]]!=i)
{
write(-1);
return 0;
}
}
arr[1]=1;
arr[2]=x[1];
for(register int i=2;i<n;i++)
{
if(arr[i-1]==x[arr[i]])
{
arr[i+1]=y[arr[i]];
}
else if(arr[i-1]==y[arr[i]])
{
arr[i+1]=x[arr[i]];
}
}
for(register int i=1;i<=n;i++)
{
f[(i-arr[i]+n)%n]++;
}
for(register int i=0;i<n;i++)
{
ans=min(ans,n-f[i]);
}
for(register int i=0;i<n;i++)
{
f[i]=arr[i+1]=0;
}
arr[1]=1;
arr[2]=y[1];
for(register int i=2;i<n;i++)
{
if(arr[i-1]==x[arr[i]])
{
arr[i+1]=y[arr[i]];
}
else if(arr[i-1]==y[arr[i]])
{
arr[i+1]=x[arr[i]];
}
}
for(register int i=n;i>=1;i--)
{
f[(i-arr[i]+n)%n]++;
}
for(register int i=0;i<n;i++)
{
ans=min(ans,n-f[i]);
}
write(ans);
return 0;
}
全部评论 3
#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=num*10+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]];//反跑直接反过来，ctrl+c&&ctrl+v } for(int i=1;i<=n;i++) { spin[((i-circle[i]+n))%n]++; ans=min(ans,n-spin[((i-circle[i]+n))%n]);//反跑反正数组不会变，一样的ctrl+c&&ctrl+v } printf("%d",ans); }3天前 来自 北京
1
有帮助，赞一个