记录编号	566545	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]篝火晚会	最终得分	100
用户昵称	冷月星云	是否通过	通过
代码语言	C++	运行时间	0.275 s
提交时间	2021-11-11 19:42:27	内存使用	6.69 MiB

#include<bits/stdc++.h>
using namespace std;
int n,p[50010],c[50010],a[50010][2],qi=0,ans=0,mx,d,b[50010];
int main(){
	freopen("fire.in","r",stdin);
	freopen("fire.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i][0]>>a[i][1];
    }
    qi=1;
    p[0]=a[1][0];
    p[1]=1;
    p[2]=a[1][1];
    ans=3; 
    qi=a[1][1];
    d=1;//初始化一号同学 
    for(;ans<n;){
         if (a[qi][0]!=d&&a[qi][1]!=d){
             cout<<"-1";
             return 0;
         }//当左侧同学不是当前同学想要的时不符合题意 
         if (a[qi][0]==d){
            d=qi;
             p[ans++]=a[qi][1];
            qi=a[qi][1];
         }
         else{
            d=qi;
            p[ans++]=a[qi][0];
            qi=a[qi][0];
         }//根据左侧同学排除右侧同学 
    }//排列出新队伍 
    if (a[p[n-1]][0]!=p[0]&&a[p[n-1]][1]!=p[0]){
         cout<<"-1";
         return 0;
    }//仅有部分同学构成一个环时不符合题意 
    for(int i=0;i<n;i++){
        b[(i-p[i]+n)%n]+=1;
        if (b[(i-p[i]+n)%n]>mx){
	   		mx=b[(i-p[i]+n)%n];
	    } 
    }//正向计算最大偏移量 
    c[0]=p[2];c[1]=p[1];c[2]=p[0];
    for (int i=3;i<n;i++){
    	c[i]=p[n+1-i];
    } //将序列转换 
    for(int i=0;i<=n;i++){
    	b[i]=0; 
    } 
    for (int i=0;i<n;i++)
    {
        b[(i-c[i]+n)%n]+=1;
         if (b[(i-c[i]+n)%n]>mx) mx=b[(i-c[i]+n)%n];
    }//反向计算最大偏移量 
    cout<<n-mx;
    return 0;
}