[NOIP2005 提高组] 篝火晚会（含代码）

[NOIP2005 提高组] 篝火晚会

题目描述

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

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

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

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

输入格式

第一行是一个整数 $n$，表示一共有 $n$ 个同学。

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

输出格式

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

样例 #1

样例输入 #1

4
3 4
4 3
1 2
1 2

样例输出 #1

2

提示

• 对于 $30\%$ 的数据，满足 $n\le 1000$；
• 对于 $100\%$ 的数据，满足 $3\le n\le 50000$。

【题目来源】

NOIP 2005 提高组第三题（洛谷）

题解

#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;
}