题解 P1053 【篝火晚会】

1124828077ccj · 2017-01-23 15:53:28 · 题解

可以用贪心来做，如果知道原序列和目标序列，算算目标序列中有几个元素和原序列不同，就是答案了。

所以要想办法构造目标序列。

可以随便放一个数，然后在它的右边放上一个他希望相邻的数（有两个，所以要分两种情况）然后就可以按照这样的方法逐个构造。

现在构造出了目标序列，但它是个圈，所以要破环成链比较，但这样效率O(n^2)，会超时。

其实，只需要知道有多少个元素和原序列相同，就能知道有几个元素不同了。

那么，对于某个目标序列里的元素a[i]，如果我们比较的时候从目标序列i-a[i]+1的位置开始，就会和原序列相同，可以f[i-a[i]+1]++;（但要注意边界），然后取所有的n-f[i]的最小值。

附代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,a[50002],b[50002],t[50002],f[50002],ans=1e9;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d%d",&a[i],&b[i]);
    for (int i=1;i<=n;i++)
    if (a[a[i]]!=i && b[a[i]]!=i || a[b[i]]!=i && b[b[i]]!=i)
    {printf("-1");return 0;}//判断是否合法
    t[1]=1;t[2]=a[1];//方案1
    for (int i=2;i<n;i++)
    if (a[t[i]]==t[i-1])t[i+1]=b[t[i]];
    else t[i+1]=a[t[i]];
    for (int i=1;i<=n;i++)
    f[(i-t[i]+1)>0?(i-t[i]+1):(n-(t[i]-i)+1)]++;
    for (int i=1;i<=n;i++)
    ans=min(ans,n-f[i]);
    memset(t,0,sizeof(t));memset(f,0,sizeof(f));
    t[1]=1;t[2]=b[1];//方案2
    for (int i=2;i<n;i++)
    if (a[t[i]]==t[i-1])t[i+1]=b[t[i]];
    else t[i+1]=a[t[i]];
    for (int i=1;i<=n;i++)
    f[(i-t[i]+1)>0?(i-t[i]+1):(n-(t[i]-i)+1)]++;
    for (int i=1;i<=n;i++)
    ans=min(ans,n-f[i]);
    printf("%d",ans);
    return 0;
}