题解 P1053 【篝火晚会】

zzzyc · 2017-10-25 10:48:06 · 题解

#include<iostream>
using namespace std;
int ans,x[500001],y[500001],n,s[500001],a[500001],b[500001],l1,l2;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
// ————————一条华丽的手动分割线———————— 
    s[1]=1; s[n]=x[1]; s[2]=y[1];
    for(int i=3;i<=n-1;i++)
        if(x[s[i-1]]==s[i-2]) s[i]=y[s[i-1]];
        else s[i]=x[s[i-1]];
// 建环，估计也只有我zz的错了这个。。。然后想了半天
// ps(一句废话):问大佬被大佬鄙视了半天。。。 
// —————————————————————————— 
    for(int i=1;i<=n;i++)
    {
        l1=i-1;l2=i+1;
        if(l1<1) l1=n;
        if(l2>n) l2=1;
        if((s[l1]!=x[s[i]] || s[l2]!=y[s[i]]) && (s[l2]!=x[s[i]] || s[l1]!=y[s[i]]))
        {
            cout<<"-1";
            return 0;
        }
    }
// 判断是不是成环了。。。
//可以在这步同时求出有多少个不符合位置的人，直接出结果
// dalao可以try一try。。。 
// ——————————————————————————
    for(int i=1;i<=n;i++)
    {
        a[(s[i]-i+n)%n]++;
        b[(s[i]+i-1)%n]++;
    }
// o(n)做法。。。烧脑。。。 
    for(int i=0;i<=n-1;i++)
    {
        if(ans<a[i]) ans=a[i];
        if(ans<b[i]) ans=b[i];
    }
    cout<<n-ans;
}