题解 P1053 【篝火晚会】

· · 题解

这道题有难度，最难想到是的贪心。

假设初始数列为 1,2,3..n

目标序列 a1,a2,a3..an

贪心：假设能够构成环，那么置换的代价一定可以等于所有不在位置上的数的个数。

举个例子，序列中没在原先位置的数，一定可以换到它应在的位置，代价为1，而那个被取而代之的数，

也一定可以换到它应有的位置

(它原先一定不在自己的位置，因为一个位置的点只能有1个，而它已被某个点取到了)。

于是O(n^2)的算法诞生了，将初始序列的状态固定，枚举置换得到的序列，每次找一遍即可。

O(n)的优化，发现许多数都不会在位置上，这些状态都浪费了。

对于置换得到的数列，找每个数距离初始状态的长，统计相同长的个数即可。

#include<cstdio>
#define MAXN 50001
int a[MAXN], b[MAXN];
int s[MAXN], cnt1[MAXN], cnt2[MAXN],ans;
int i,j,n;
int main()
{
    scanf("%d",&n);
    for (i=1; i<=n; i++)
      scanf("%d%d",&a[i],&b[i]);
    s[1]=1; s[n]=a[1]; s[2]=b[1];
    for (i=3; i<n; i++)
        if (a[s[i-1]]==s[i-2]) s[i]=b[s[i-1]];
        else s[i]=a[s[i-1]];
    for (i=1; i<=n; i++)
    {
        int t1=i+1, t2=i-1;
        if (t1>n) t1=1;
        if (t2<1) t2=n;
        if ((s[t1]!=a[s[i]] || s[t2]!=b[s[i]]) && (s[t2]!=a[s[i]] || s[t1]!=b[s[i]]))
        {
            printf("-1");
            return 0;
        }
    }
    for (i=1; i<=n; i++)
    {
        cnt1[(s[i]-i+n)%n]++;
        cnt2[(s[i]+i-1)%n]++;
    }
    for (i=0; i<n; i++) //注意注意，%n后存放的地址为0..n-1。否则会爆第10个点 
    {
        if (ans<cnt1[i]) ans=cnt1[i];
        if (ans<cnt2[i]) ans=cnt2[i];
    }
    printf("%d",n-ans);
    return 0;
}