这道题有一个坑
m个数不连续,随意指定
所以
只要找出不一样的需要摆正的数就行了
首先要求出目标序列
在求的过程中判断能否达到目标序列
因为一定能够达到目标序列
所以只要求出是否有目标序列就行了
a[2]设成l[1],r[1]都可以
依次放置,补全序列
vis防止多个人想和一个人交朋友
不一样的数的数量在
从1开始的序列
从2开始的序列
…
从n开始的序列
不一定一样
但是目标序列和1,2…n-1,n都是环的形式
没有从谁开始的区别
都有可能成为最后的答案
从中取一个不一样的数最少的
对它进行一次代价为 不一样的数的数目 的移动
最小的不一样的数的数目就是答案
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
int l[50055];
int r[50055];
int a[50055];
int vis[50055];
int d1[50055];
int d2[50055];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d %d",&l[i],&r[i]);
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
a[1]=1;
a[2]=l[1];
vis[1]=vis[l[1]]=1;
for(int i=2;i<=n-1;i++)
{
if(l[a[i]]==a[i-1])
{
a[i+1]=r[a[i]];
vis[r[a[i]]]=1;
continue;
}
if(r[a[i]]==a[i-1])
{
a[i+1]=l[a[i]];
vis[l[a[i]]]=1;
continue;
}
break;
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
cout<<"-1";
return 0;
}
}
if(a[n]!=r[1])
{
cout<<"-1";
return 0;
}
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
for(int i=1;i<=n;i++)
{
d1[(a[i]-i+n)%n]++;
d2[(i+a[i]-1)%n]++;//逆时针的时候,n,n-1,...2,1,i的位置对应了目标序列中的n-a[i]+1的位置,两者的距离为 (i-(n-a[i]+1)+n)%n-->(i+a[i]-1)%n
}
int ans=0;
for(int i=0;i<=n-1;i++)
ans=max(ans,max(d1[i],d2[i]));
cout<<n-ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int l[50055];
int r[50055];
int a[50055];
int vis[50055];
int d1[50055];
int d2[50055];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d %d",&l[i],&r[i]);
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
a[1]=1;
a[2]=r[1];
vis[1]=vis[r[1]]=1;
for(int i=2;i<=n-1;i++)
{
if(l[a[i]]==a[i-1])
{
a[i+1]=r[a[i]];
vis[r[a[i]]]=1;
continue;
}
if(r[a[i]]==a[i-1])
{
a[i+1]=l[a[i]];
vis[l[a[i]]]=1;
continue;
}
break;
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
cout<<"-1";
return 0;
}
}
if(a[n]!=l[1])
{
cout<<"-1";
return 0;
}
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
for(int i=1;i<=n;i++)
{
d1[(a[i]-i+n)%n]++;
d2[(i+a[i]-1)%n]++;//逆时针的时候,n,n-1,...2,1,i的位置对应了目标序列中的n-a[i]+1的位置,两者的距离为 (i-(n-a[i]+1)+n)%n-->(i+a[i]-1)%n
}
int ans=0;
for(int i=0;i<=n-1;i++)
ans=max(ans,max(d1[i],d2[i]));
cout<<n-ans;
return 0;
}