篝火晚会 题解

这个题比较难。
想到正解思路并不容易，正解的第一点就是最后的答案事实上应该是目标序列和原序列不相同的数的最小值。简要证明一下：假设目标序列上的元素X和原序列相同位置不相同，那么就只需要1个代价来把它恢复到正确的位置上，其它的亦然。
然后我们就想到了这样一个思路，目标序列构造好了之后，由于它的开头不一定，有2*N种序列需要比较，我们就逐一比较，这就是O（N^2）的算法。
显然对于50000的数据，这样是不会过的。那么还有一个思路，就是求原序列和目标序列之间的距离，并将之记录下来，然后就是O（N）的时间复杂度，然后输出N-min(count[length])啦。

AC代码

#include<iostream>
using namespace std;
int i,j,m,n,temp;
int a[50001],x[50001],y[50001];
int gs[50001],gs2[50001];

int r()
{
    int ans=0,f=1;
    char ch;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ans*=10;
        ans+=ch-'0';
        ch=getchar();
    }
    return ans*f;
}
int main(){
    n=r();
    for(i=1;i<=n;i++) {
        x[i]=r(),y[i]=r();
    }
    a[1]=1,a[2]=x[1];
    for(i=3;i<=n;i++) {
        if(x[a[i-1]]==a[i-2]) a[i]=y[a[i-1]];
        else a[i]=x[a[i-1]];
    }
    int le,ri;
    for(i=1;i<=n;i++){
        le=i-1;
        ri=i+1;
        if(!le)
        le=n;
        if(ri==n+1)
        ri=1;
        if((x[a[i]]!=a[ri]||a[le]!=y[a[i]])&&
        (y[a[i]]!=a[ri]||a[le]!=x[a[i]]))
        {
            cout<<-1;
            return 0;
        }
    }
    int dis1,dis2;
    for (i=1; i<=n; i++)
    {
        dis1=(a[i]-i+n)%n;
        dis2=(a[i]+i-1)%n;
        gs[dis1]++;
        gs2[dis2]++;
    }
    int ans=0;
    for (i=0; i<n; i++) 
    {
        if (ans<gs[i]) ans=gs[i];
        if (ans<gs2[i]) ans=gs2[i];
    }
    cout<<n-ans;
    return 0;
}