洛谷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);
}