题解 P1053 【篝火晚会】

· · 题解

题面

https://www.luogu.org/problemnew/show/P1053 。

题目描述

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有 n 个同学，编号从 1 到 n 。一开始，同学们按照 1,2,…,n 的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：

(b_1, b_2,... b_{m-1}, b_m)

这里 m 的值是由佳佳决定的，每次命令 m 的值都可以不同。这个命令的作用是移动编号是 b_1,b_2,…, b_m 的这 m 个同学的位置。要求 b_1 换到 b_2 的位置上， b_2 换到 b_3 的位置上，……，要求 b_m 换到 b_1的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置，那么这个命令的代价就是 m 。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

输入输出格式

第一行是一个整数 n\;(3 \leq n \leq 50000) ，表示一共有 n 个同学。

其后 n 行每行包括 2 个不同的正整数，以一个空格隔开，分别表示编号是 1 的同学最希望相邻的两个同学的编号，编号是 2 的同学最希望相邻的两个同学的编号，……，编号是 n 的同学最希望相邻的两个同学的编号。

输入输出样例

数据范围

对于 30\% 的数据，n \leq 1000 ；

对于全部的数据，n \leq 50000 。

题解

首先我们可以通过给出来的相邻关系把这个环给建出来。

怎么建呢？首先先设 a_i 表示这个环中的第 i 个人的原来的编号（1~n）， l_i 和 r_i 分别是这个人想要的与之相邻的两个人的编号。那么我们就可以先让 a_n=l_1,a_1=1,a_2=r_1。因为这个环是可旋转的qwq。

然后如果 a_{i-2} 是 a_{i-1} 期望的左边，那么 a_i 就应是 a_{i-1} 所期望的右边，所以 a_i=r_{a_{i-1}}。

反之，如果 a_{i-2} 是 a_{i-1} 期望的右边，那么 a_i 就应是 a_{i-1} 所期望的左边，所以 a_i=l_{a_{i-1}}。

如果都不满足的话说明这样的环不存在，输出 -1 。

这一部分的代码是这样的：

a[n]=l[1],a[1]=1,a[2]=r[1];
for(int i=3;i<=n-1;i++)
{
    if(a[i-2]==l[a[i-1]])
    {
        a[i]=r[a[i-1]];
    }
    else if(a[i-2]==r[a[i-1]])
    {
        a[i]=l[a[i-1]];
    }
    else
    {
        printf("-1");
        return 0;
    }
}

然后就是求答案辣！

我们用 dis1_i 表示从原位置走到目标位置顺时针要走 i 步的人有多少个。

并且用 dis2_i 表示从原位置走到目标位置逆时针要走 i 步的人有多少个。

易得，对于一个人 i，他会对 dis1_{(i-a_i+n)\;mod\;n} 以及 dis2_{(i+a_i+n)\;mod\;n} 均产生 1 的贡献。然后我们就可以把它们统计出来了。

下面是这一部分的代码。

for(int i=1;i<=n;i++)
{
    dis1[(i-a[i]+n)%n]++;
    dis2[(i+a[i]+n)%n]++;
}

因为若有 k 个人不在目标位置上，则需要 k 的代价。所以有

ans=n-\max_{i=0}^{2n} max(dis1_i,dis2_i)

求一下就可以了。

完整代码：

#include <cstdio>
int l[1000001],r[1000001];
int a[1000001],cx[1000001];
int dis1[1000001],dis2[1000001];
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    int n=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&l[i],&r[i]);
    }
    a[n]=l[1],a[1]=1,a[2]=r[1];
    for(int i=3;i<=n-1;i++)
    {
        if(a[i-2]==l[a[i-1]])
        {
            a[i]=r[a[i-1]];
        }
        else if(a[i-2]==r[a[i-1]])
        {
            a[i]=l[a[i-1]];
        }
        else
        {
            printf("-1");
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        dis1[(i-a[i]+n)%n]++;
        dis2[(a[i]+i+n)%n]++;
    }
    int ans=0;
    for(int i=0;i<=n*2;i++)
    {
        ans=max(ans,max(dis1[i],dis2[i]));
    }
    printf("%d",n-ans);
    return 0;
}