题解 P1053 【篝火晚会】

· · 题解

博客 感觉还是博客里的格式好看一点，这里的换行好像被吞了

题目

题解：

模拟，构造出整个数列，要求的就是这个数列需要经过多少次操作得到 但是，这其实是一个环，编号为1的可以放任意一个位置，每一位都可以右移一位，最右边的一位移到第一位（后文直接叫右移）。 而且，第一个人可以选择左边a[1]，右边b[1]，也可以左边b[1]，右边a[1]，所以环还可以倒过来。 比如题中所给数据： 4 3 4 4 3 1 2 1 2 假设第一位是1，那整个数列可以是1 3 2 4，也可以是1 4 2 3。 可以发现，右边的倒过来，就变成3 2 4 1，和左边是一样的。 考虑正着的情况（反着也一样） 假设右移k次是最优解，右移过以后与原数列有t个不同，那交换的代价就是t，那就可以设ans[i]表示右移i位后与原数列有ans[i]个相同， 那么答案=max{n-ans[i]}=n-max{ans[i]}

标程：

#include<bits/stdc++.h>
using namespace std;
const int N=50002;
int n,i,ans,a[N],b[N],h[N],ans1[N],ans2[N];
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
inline void write(int a){if(a>=10)write(a/10);putchar(a%10|48);}
inline void writeln(int a){if(a<0)a=-a,putchar('-');write(a);puts("");}
int main(){
    n=read();
    for (i=1;i<=n;i++) a[i]=read(),b[i]=read();
    h[1]=1;h[2]=b[1];h[n]=a[1];
    for (i=3;i<n;i++)
        if (a[h[i-1]]==h[i-2]) h[i]=b[h[i-1]];
        else if (b[h[i-1]]==h[i-2]) h[i]=a[h[i-1]];
        else{
            printf("-1");
            return 0;
        }
    for (i=1;i<=n;i++) ans1[(h[i]-i+n)%n]++,ans2[(h[i]+i)%n]++;
    //计算ans，其中ans1是正着来的，ans2是倒着
    for (i=0;i<n;i++) ans=max(ans,max(ans1[i],ans2[i]));
    printf("%d",n-ans);
}