题解 P1053 【篝火晚会】

· · 题解

这一题...... 第一眼看过去...... 不会做啊什么神仙题目......

那么试着套一套常见思路......

等等这一题环这个条件好像没有什么用诶QWQ

等等一个人最多只会产生一点贡献诶QWQ

等等这一题好像可以反向思考诶QWQ

撑死是个蓝题诶(雾)

等等我一开始说了什么......

好吧那么我们现在进入正题.

首先我们发现这个环好像没有什么用直接拆了得了.

然后我们最后答案最多只有两种, 一种正着, 一种反着...... 我们可以容易地求出这两种顺序, 我们将这两种排列称作"理想的"......

然后我们发现其实一次操作足以解决所有问题: 所有需要移动的都可以只移动一次.

那么我们现在就是要最小化需要移动的人的个数QWQ

然后我们可以转换为最大化不需要移动的人的个数.

我们发现其实任意两个不需要移动的人只见的距离都是定值, 也就是说, 他们之间的距离和最终结果中他们两个的距离是一样的, 那么每个人到理想排列中他们的位置的距离都相等, 因为其实是个环, 所以其实不一定完全是理想排列, 还可以是理想排列旋转之后的结果.

然后我们只需要求出每一个人目前的位置到他理想排列中位置的距离就好了, 然后找出数量最多的那一波人, 让他们不动, 剩下的人去跑腿.

但是注意到理想排列有两种...... 所以双倍快乐要多敲一点什么的......

要是你没看懂, 可以......

  1. 再看一次

  2. 看一下代码

放一下代码......

#include<iostream>
#include<algorithm>
using namespace std;
namespace fio {
    streambuf* in = cin.rdbuf();
    char bb[1000000], * s = bb, * t = bb;
#define gc() (s==t&&(t=(s=bb)+in->sgetn(bb,1000000),s==t)?EOF:*s++)
    inline int read() {
        int x = 0;
        char ch = gc();
        while (ch < 48)ch = gc();
        while (ch >= 48)x = x * 10 + ch - 48, ch = gc();
        return x;
    }
}using fio::read;
int n;
int arr[100005], brr[100005], crr[100005];
// arr, brr都是左右的人, crr是第i个位置的人.
// 这是我写过最丑陋的代码之一......
int cnt[100005], cntx[100005];// 统计到理想排列的距离为x的人数, 选出最多的让他们不动
int fm[100005];
int main() {
    n = read();
    for (int i = 1; i <= n; i++)arr[i] = read(), brr[i] = read();
    crr[2] = arr[1], crr[n] = brr[1], crr[1] = 1;
    for (int i = 2; i <= n; i++) {
        if ((crr[i - 1] != arr[crr[i]] && crr[i - 1] != brr[crr[i]]))cout << -1, exit(0);
        if (crr[i - 1] == arr[crr[i]])crr[i % n + 1] = brr[crr[i]];
        else crr[i % n + 1] = arr[crr[i]];
    }// 计算理想排列
    for (int i = 1; i <= n; i++) {
        int l = crr[(i - n - 1) % n + n], r = crr[i % n + 1];
        if (min(l, r) != min(arr[crr[i]], brr[crr[i]]) || max(l, r) != max(arr[crr[i]], brr[crr[i]]))cout << -1, exit(0);
    }// 检验理想排列的合法性
    for (int i = 1; i <= n; i++)cnt[(i - crr[i] + n) % n]++, cntx[abs(n - i - crr[i] + 1 + n) % n]++;// 统计一波
    int ans = 0;
    for (int i = 0; i < n; i++)ans = max(ans, max(cnt[i], cntx[i]));
    cout << n - ans;// 记住我们把答案反了过来
}