Time Limit: 1 second

Memory Limit: 50 MB

【问题描述】

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有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+1行；

第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。

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

【输出】

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

【输入样例】

4

3 4

4 3

1 2

1 2

【输出样例】

2

【 数据规模】

30%的数据满足：n <= 1000；

100%的数据满足：n <= 50000。

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=b503

【题解】



首先,需要通过给出的n个人的需求;

判断出每个人的位置;

这里根据所给的关系,得出每个人的度数;

显然,构成一个环的要求是,每个人的度数都为2;

但是这样还不够,还得n个点都是联通的才行;不然两个独立的环

每个人的度数也都是2,但是不符合要求的;

然后根据输入得出这张换的一维形式;

即a[i]=t;表示第i个位置的人是t;

又一开始a[i]=i;

则先找出一开始不在自己位置上的人的个数y;

根据那个规则可以猜测y就是答案了;

但是这里一个环转换成一维的形式有N种;

你得算出每一种,不在自己位置上的人的个数;

然后求出最小值;

这里有一个思维的过程;

即先求出在自己位置上的人的最大个数的序列;

然后用n减去这个最大个数;

剩下的就是不在自己位置上的人数最小的人数了;

这个在自己位置上的人的最大个数可以通过偏移量来算;

即

随便选一个一维序列

b[1],b[2]…b[n];

表示第i个人要到哪一个位置;

然后对于每一个人

dic[b[i]-i]++;

这就表示第i个人从它原来的位置到它想要的位置需要把整个序列移动多少;

然后找最大的dic;

这个dic就是在自己想要在的位置上的人数的最大值;

因为有x个人他需要偏移dic[x]个位置就能回到自己的位置上,那么就整体把这个序列偏移dic[x]个位置就好;

假设N=7

则

向左偏移2格就相当于向右移动5格;

所以对于b[i]-i小于0的情况,直接加上n就好

即dic[(b[i]-i+n)%n]++;

然后再把这个随便选的环化线的序列b翻转一下(用reverse函数倒序一下就好);

再做一下上述过程；

因为我们只是左右偏移,还没办法覆盖翻转的情况;

所以还要再翻转一下才能把所有的情况都考虑到;

最后用n减去那个值就是答案了;



【完整代码】

#include <map>

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int MAXN = 50000+100;

int a[MAXN][2],du[MAXN],b[MAXN],cnt,n;

bool bo[MAXN];

map <int,int> dic;

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);

    rep1(i,1,n)

    {

        rei(a[i][0]),rei(a[i][1]);

        du[a[i][0]]++,du[a[i][1]]++;

    }

    rep1(i,1,n)

        if (du[i]!=2)

        {

            puts("-1");

            return 0;

        }

    int now = cnt = 1;

    b[1] = now;

    bo[1] = true;

    while (cnt < n)

    {

        int x = a[now][0];

        if (bo[x])

            x = a[now][1];

        if (bo[x])//如果往两个方向走都是走过的点

        {//而且还没有走满n个点,就说明有多个独立的环

            puts("-1");

            return 0;

        }

        bo[x] = true;

        now = x;

        b[++cnt] = x;

    }

    rep1(i,1,n)

        dic[(b[i]-i+n)%n]++;

    int num = 0;

    rep1(i,0,n-1)

        num = max(num,dic[i]);

    dic.clear();

    reverse(b+1,b+1+n);

    rep1(i,1,n)

        dic[(b[i]-i+n)%n]++;

    rep1(i,0,n-1)

        num = max(num,dic[i]);

    printf("%d\n",n-num);

    return 0;

}