题解 P1053 【篝火晚会】

· · 题解

NOIP2005 提高组——篝火晚会

​ by - Actinoi

2019/6/22

为获取最佳阅读效果，建议访问https://www.actinoi.com/2019/06/22/NOIP2005提高组——篝火晚会/

​ 本题有一个坑，那就是移动的人不需要连续。然后。。。知道这个坑点之后，我们很容易想到最优解，那就是化环为链，构建目标链与初始链，然后找到目标链与初始链中不一样的人的总数，用总人数 - 相同的人数就是需要调换的人数。至于为什么能够在 O(N) 内完成操作，下图可以做一个更加直观的说明。

例如，初始环是左边的这个环，目标环是右边的环，如箭头所示的路径，我们可以通过 （2,5,6） 的指令 O(N) 完成变换。

    但是，环是可以旋转的，因此我们并不知道怎样转动是最优的。我们便可以考虑以每个点为起点进行搜索，因此，一个绝佳的 O(N^2) 的算法便出炉啦！

    无疑，这个算法会让我们看到一片 TLE 。所以，我们便可以考虑优化这个算法。

    如上图，我们从 1 开始构建一条初始链，再构建一条目标链。

初始链： 1, 2, 3, 4, 5, 6

目标链： 1, 6, 3, 4, 2, 5

我们将两条链对应的数相减，取绝对值，便可以得到：

差值：0, 4, 0, 0, 3, 1

​    在这条差值中， 0 出现的次数的是最多的。那么，若果有一条差值 1 出现的次数是最多的，那么，这意味着什么？无疑，将那条链转动 1 个单位，我们便可以得到最优解了！而在程序中，我们并不需要真正转动，只需要统计出现次数最多的差值 c，这就代表初始环在转动 c 个单位之后，在同一个位置上的人数与目标环重合的最多，然后用总人数 n 减去差值 c 出现总次数，便是我们需要调换的人的数w量，也就是我们想要的答案 m 啦！

等等！

​    这既然是一个环，那么，会不会构建目标链得到的结果不一样呢？的确是这样滴。还是以上图为例，从 1 开始我们可以得到 1, 6, 3, 4, 2, 5 与 1, 5, 2, 4, 3, 6 两条链。那这怎么办呢？既然我们不确定我们拥有的目标链是顺时针构建的还是逆时针构建的，我们便可以在计算差值时顺时针与逆时针各跑一边，然后取最大值。我们用 target 数组存储目标链，用 initial 数组存储初始链，便可以用 (target[i] - initial[i] + n) % n 顺时针从 1 ～ n 跑一遍，再用 (target[i]- initial[n - initial[i] + 1] + n) % n 逆时针从 n ～ 1 跑一遍差值，然后找出最大的差值。

​    那么，什么时候不能符合每个同学的愿望呢？其实，只要构出目标环，便一定可以用玄学的方法使每个同学满意。那么，只有在构不成目标环的时候才输出 -1 。那什么时候构不成目标环呢？无疑，第 i 个同学想挨着的那个人不想挨着他（好一个悲伤的故事）的时候才构不成环，此时输出 -1。所以，我们直接判断第 i 个同学左右两边是否还有空座就可以，如果没有的话，那就。。。输出 -1 了。

最后附上代码：

#include <iostream>
using namespace std;
int target[50001], initial[50001], people[50001][3], pluss[50001], minuss[50001]; //存储目标链，初始链，每个人最希望相邻的两个同学的编号，正序相同人数以及逆序相同人数
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch=='-')
            w=-1;
    ch=getchar();
    }
    while(ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int main() {
    int n;
    n = read();
    for (int i = 1; i <= n; i++) //读入编号是 i 的同学最希望相邻的两个同学的编号
        people[i][1] =read(), people[i][2] = read();
    target[1] = 1;
    target[2] = people[1][2]; //构建目标链
    initial[1] = 1;
    initial[n] = n; //构建初始链
    for (int i = 2; i <= n - 1; i++) {
        initial[i] = i; //构建初始链
        if (target[i - 1] == people[target[i]][1])
            target[i + 1] = people[target[i]][2];
        else if (target[i - 1] == people[target[i]][2])
            target[i + 1] = people[target[i]][1]; //构建目标链
        else{
            cout << -1 << endl; //第 i 个人希望相邻的人旁边没有空位了，无法构建目标链（一个悲伤的故事）
            return 0;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        pluss[(target[i] - initial[i] + n) % n]++; //顺时针从 1 ~ n 跑一遍
        minuss[(target[i]- initial[n - initial[i] + 1] + n) % n]++; //逆时针从 n ~ 1 跑一遍差
    }
    for (int i = 0; i <= n - 1; i++)
        ans = max(ans, max(pluss[i], minuss[i])); //找差值人数最多的
    cout << n - ans; //总人数 - 不用移动的人数 = 需要移动的人数，也就是答案
    return 0;
}