洛谷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=;
int n,i,ans,a[N],b[N],h[N],ans1[N],ans2[N];
inline char gc(){
    static char buf[],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x=,fl=;char ch=gc();
    for (;ch<||ch>;ch=gc())if(ch=='-')fl=-;
    for (;<=ch&&ch<=;ch=gc())x=(x<<)+(x<<)+(ch^);
    return x*fl;
}
inline void write(int a){if(a>=)write(a/);putchar(a%|);}
inline void writeln(int a){if(a<)a=-a,putchar('-');write(a);puts("");}
int main(){
    n=read();
    for (i=;i<=n;i++) a[i]=read(),b[i]=read();
    h[]=;h[]=b[];h[n]=a[];
    for (i=;i<n;i++)
        if (a[h[i-]]==h[i-]) h[i]=b[h[i-]];
        else if (b[h[i-]]==h[i-]) h[i]=a[h[i-]];
        else{
            printf("-1");
            return ;
        }
    for (i=;i<=n;i++) ans1[(h[i]-i+n)%n]++,ans2[(h[i]+i)%n]++;
    //计算ans，其中ans1是正着来的，ans2是倒着
    for (i=;i<n;i++) ans=max(ans,max(ans1[i],ans2[i]));
    printf("%d",n-ans);
}