P1053 篝火晚会

· · 题解

p.s.非常抱歉之前的题解出现了错误，少判断了最后一位是不是满足要求，现已更正，感谢 @G_keng 同学热心指出并提供hack数据。

题目https://www.luogu.org/problemnew/show/P1053

这个题最大的坑点在于：m个人可以不连续！！！！

这个锅题目描述得背，描述里b1,b2,...bm实在是太规则了，使我以为操作必须得从1开始，并且要连续...

然后就没那么难了，我们考虑，把环破成链，假设有k个数在当前链和目标链中的位置相同，那么就有n-k个不相同的，我们每次操作只对这n-k个数进行，我们最优可以做到每操作x个数，就一次性把这x个数全放到正确位置上，比如说：

1 2 3 4 5 6 7 8 9 10 -> 1 8 2 7 5 3 6 4 10 9

先通过（10,8,1）-> 8 2 3 4 5 6 7 10 9 1

再通过（3,5,4,7） 就可以了。

（注意是环：8 2 7 5 3 6 4 10 9 1和1 8 2 7 5 3 6 4 10 9是一样的）

这样就做到了每次只操作位置不对的，实现了最小化代价。

所以，结论就是：把初始链变成目标链的最小代价为n-k。（k的意义同上）

那么我们只需要O(n)搞出目标链的两种情况，然后每次右移（左移）之后与1,2,3,...,n作对比，求得最小的n-k。

但这样是O(n^2)的......

我们可以优化：

初始链 1 2 3 4 5 6
目标链 4 2 3 1 5 6
差值 3 0 0 3 0 0

差值指的是需要右移的次数

这个例子下，可以发现，不管怎么右移，差值虽变化，但相同的一直相同，不同的一直不同，那么我们就可以只搞出一个目标链，O(n)求一下此时的差值，然后找出其中相同个数最多的就可以了。

具体做法就是：对于所给的数据，我们可以通过O(n)建一条链，如果建不出来，输出-1。建出来之后，与1,2,3...,n和n,n-1,...2,1分别求一遍差值，然后统计最大的，然后，完了。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int Maxn=50010;
int Dv1[Maxn],Dv2[Maxn];
//分别表示与1,2,...,n和n,n-1,...,2,1的差值
int vis[Maxn];
int c[Maxn];//目标链
int l1[Maxn],l2[Maxn];
int si=1,n,ans=0;
inline int read()//读入优化
{
    int fl=1,rt=0; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') fl=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){rt=rt*10+ch-'0'; ch=getchar();}
    return fl*rt;
}
void Build()//建目标链
{
    c[1]=1; c[2]=l1[1]; vis[c[1]]=vis[c[2]]=1;
    for(int i=2;i<=n-1;i++)
    {
        if(c[i-1]==l1[c[i]]) c[i+1]=l2[c[i]],vis[c[i+1]]=1;  
        else if(c[i-1]==l2[c[i]]) c[i+1]=l1[c[i]],vis[c[i+1]]=1;
        else 
        {
            si=0;
            printf("-1\n"); return ;
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) si=0,printf("-1\n");
    //前面没判断c[n]同学的需求是否满足，这里判断一下。
    if((c[1]==l1[c[n]]&&c[n-1]!=l2[c[n]])||(c[1]!=l1[c[n]]&&c[n-1]==l2[c[n]])) si=0,printf("-1\n");
    else if((c[1]==l2[c[n]]&&c[n-1]!=l1[c[n]])||(c[1]!=l2[c[n]]&&c[n-1]==l1[c[n]])) si=0,printf("-1\n");
}
void Simulation()//求答案
{
    for(int i=1;i<=n;i++)
    {
        Dv1[(c[i]-i+n)%n]++;
        Dv2[(c[n-i+1]-i+n)%n]++;
    }
    for(int i=0;i<=n-1;i++) ans=max(ans,max(Dv1[i],Dv2[i]));
    printf("%d\n",n-ans);
}
void read_ini()
{
    n=read();
    for(int i=1;i<=n;i++) l1[i]=read(),l2[i]=read();
    Build();
    if(si) Simulation();
}
int main()
{
    read_ini();
    return 0;
}

最后推荐一个ppt，包括noip2005所有题目的题解 Rp++ https://wenku.baidu.com/view/878beb64783e0912a2162aa7.html?qq-pf-to=pcqq.c2c