记录编号	45206	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]篝火晚会	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.332 s
提交时间	2012-10-22 20:24:52	内存使用	4.10 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int NSIZE=50001;
int mate1[NSIZE]={0},mate2[NSIZE]={0},goal[NSIZE]={0};//两个希望相邻的,目标状态
int pos[NSIZE]={0},rev[NSIZE]={0};//第i个元素分别表示正序逆序与目标位置之差为i的个数
int n;
int findmax(int s[]){
	int i,ans=-1;
	for(i=0;i<n;i++) if(s[i]>ans) ans=s[i];
	return ans;
}
bool init(void){
	int i,x,y;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>mate1[i]>>mate2[i];
		mate1[i]--,mate2[i]--;
	}
	goal[1]=mate2[0];
	for(i=1;i<n-1;i++){
		x=mate1[goal[i]],y=mate2[goal[i]];
		if(x==goal[i-1]) goal[i+1]=y;
		else if(y==goal[i-1]) goal[i+1]=x;
		else return 0;//对不上就返回0
	}
	x=mate1[goal[n-1]],y=mate2[goal[n-1]];
	if((x==goal[n-2]&&y==goal[0])||(x==goal[0]&&y==goal[n-2])) return 1;
	return 0;
}
int work(void){
	int i,x,y,ans,temp;
	for(i=0;i<n;i++){
		x=i-goal[i];//目标减去原来的
		if(x<0) x+=n;
		pos[x]++;
		y=i-(n-goal[i]);
		if(y<0) y+=n;
		rev[y]++;
	}
	x=findmax(pos),y=findmax(rev);//再利用╮(╯▽╰)╭
	temp=(x>y)?x:y;
	temp=n-temp;
	return temp;
}
int main(){
	freopen("fire.in","r",stdin);
	freopen("fire.out","w",stdout);
	if(!init()) goto FAIL;//若失败就输出-1
	cout<<work()<<endl;
	return 0;
	FAIL:;
	cout<<"-1"<<endl;
	return 0;
}