题解 P1053 【篝火晚会】
首先要吐糟，一开始以为每次换的人必须是连续的。。。。
本来看了题完全没思路，因为数据太水就自己手造了个数据，然后造着造着发现是个建一个环再判断的问题。
用自己手造的例子来说明吧：
6
3 4
5 6
1 5
1 6
2 3
2 4画出来应该是个这样的图【有点丑我尽力了。。】：
然后原本的那个圈应该是这样的：
所以，我们要换的人就是不在应该在的位置的人。
其实所有不在应该在的位置的人都用1的代价就可以过去，因为所有不在应该在的位置的人连起来肯定是一个圈，一起换就可以，所以我们要求的答案就是有几个人不在应该在的位置。
我用的深搜来把期望圈存到数组里，把1定为初始位置，具体实现可以在下面看代码。
然后我本来以为就是存两个数组，分别是初始圈和期望圈，依次比较是否相同就可以，然后就华丽丽的WA了，然后我发现，不只是要比较这两个数组，因为还有逆时针和顺时针的问题。
还是我这个例子：
初始圈存为：1 2 3 4 5 6；
期望圈存为：1 3 5 2 6 4；这样的话答案就是5，但其实是4，因为如果逆时针来存：
初始圈可以存为：1 6 5 4 3 2；
期望圈依然存为：1 3 5 2 6 4；这样的话答案就是4了。
所以存两个数组存逆序和顺序来比较，取最小值。
改过之后还是华丽丽的WA了。。。。。
然后我们进一步发现，这个不仅仅有顺时针还是逆时针的问题，这个还有不对齐的问题。
这个时候我的例子就不行了，随便举个例子。
初始圈为：1 2 3 4 5 6；
期望圈为：2 3 4 5 6 1；如果是一一区配的话，答案应该是6，但其实我们知道，只要向旁边转一下就对齐了。
图示说明【这图好像更丑了。。。】：
解决的办法就是，用一个dis数组，来存每个点到它应该在的位置的距离，当几个点距离相同时，也就是转一下，这几个点就可以都对齐。所以我们求出最多有几个点相同距离，最终答案就是总数-相同人数。
要注意的是，判断距离时依然要分两组，顺时针和逆时针都要判断一下。
方法：顺时针时，期望圈数组中第i个人，初始时应该在b[i],所以距离为（i-b[i]）,为了使距离都在0~n-1之间，写为（i-b[i]+n）%n;
逆时针时，期望圈数组中第i个人，初始时应该在（n-b[i]+1）的位置【这里其实是让n作为初始圈第1个位置】同理，写为（n-b[i]+1+n）%n;
另外判断是否无解：某个人期望一块坐的人，期望一块坐的人不是他。emmm有点绕，就是某个人期望一块坐的人不想和他坐在一起【反正是个悲伤的故事】
放代码，细节都注释在代码里【代码很丑希望不要嫌弃。。】：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int n,a[50005],b[50005],c[50005],t,ans;//b数组来存期望圈，a和c来存希望坐在一起的两个人
int deg[50005],dis[50005],sum[50005];
void dfs(int u,int fa)
{
b[++t]=u;
if((a[u]==1&&c[u]==fa)||(c[u]==1&&a[u]==fa))return;//如果下一个是1就说明这个圈找完了【找了一圈回去了】
if(a[u]!=fa)dfs(a[u],u);
else dfs(c[u],u);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>c[i];
for(int i=1;i<=n;i++)
if((c[a[i]]!=i&&a[a[i]]!=i)||(a[c[i]]!=i&&c[c[i]]!=i))//如果我希望一块坐的人不想和我一块坐，就无解
{cout<<-1<<endl;return 0;}
b[1]=1;
t=1;
dfs(a[1],1); //把1设为第一个数，从1的下一个人开始深搜
for(int i=1;i<=n;i++)
{
dis[b[i]]=(i-b[i]+n)%n;//顺时针判断距离
sum[dis[b[i]]]++;
}
for(int i=1;i<=n;i++)ans=max(ans,sum[i]); //用sum数组存这个距离的人数，取最大值
memset(sum,0,sizeof(sum));
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;i++)
{
dis[b[i]]=(i-(n-b[i]+1)+n)%n;//逆时针判断距离
sum[dis[b[i]]]++;
}
for(int i=1;i<=n;i++)ans=max(ans,sum[i]);
cout<<n-ans<<endl;
return 0;
}还有什么不清楚或者错误的地方欢迎私信~~