题目描述

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：(b1, b2,... bm -1, bm)这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，……bm -1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？

输入描述:

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

输出描述:

包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。

示例1

输入
4
3 4
4 3
1 2
1 2
输出
2

备注

对于30%的数据，；
对于全部的数据，。

解答

首先我们可以通过给出来的相邻关系把这个环给建出来。
怎么建呢？首先先设 表示这个环中的第个人的原来的编号， 和  分别是这个人想要的与之相邻的两个人的编号。那么我们就可以先让  。因为这个环是可旋转的qwq。
然后如果  是  期望的左边，那么 就应是 所期望的右边，所以  。
反之，如果  是  期望的右边，那么  就应是  所期望的左边，所以  。
如果都不满足的话说明这样的环不存在，输出  。
这一部分的代码是这样的： 
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[(i+a[i]+n)%n]++;
}
因为若有 个人不在目标位置上，则需要  的代价。所以有
求一下就可以了。
完整代码： 
#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;
}


来源：钟梓俊