题解：CF220C Little Elephant and Shifts

__ikun__horro__ · 2024-12-30 10:19:48 · 题解

Solution

我们先来观察样例 #2：

4
2 1 3 4
3 4 2 1

先求出 b 数组每一次滚动和 a 数组每个数位置的差值（不取绝对值）：

容易发现，每两轮相邻的操作间，n-1 个数字加上 1，还有一个数字减去了 (n-1)。

我们可以用一个 \text {mutiset} 维护所有的位置差值。而且大部分的数字都是加上 1 的，所以我们可以用一个偏移量 d，第 i 轮的偏移量 d=i-1。使用 x-d 来维护 x 这个数，这样每轮只需要将一个数减去 n。

这样，我们每一轮只需取出一个最接近 -d 的数 x，输出 | x+d | 即可。

那么每次到底要让哪一个数减去 n 呢？观察一下，第 i 轮就让 b_i 所对应的数减去 n。这样就做完了。

注意：\text{multiset} 去掉数字时 \text{erase} 函数里要放指针，否则会删除值相同的所有的数。

Code

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, a[N], b[N], p[N];
multiset<int> mango;

inline void sol() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }

    auto calc = [=] (int x) {
        return p[b[x]] - x;
    };

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        mango.insert(calc(i));
    }

    for (int i = 1; i <= n; i++) {
        int delta = i - 1;

        // for (auto i : mango) {
        //  cout << i << " ";
        // }
        // cout << "\n";
        // for (auto i : mango) {
        //  cout << i + delta << " ";
        // }
        // cout << "\n";

        auto it = mango.lower_bound(-delta);
        int Min = 0x3f3f3f3f3f3f3f3f;

        if (it != mango.end()) {
            Min = min(Min, abs(*it + delta));
        }
        if (it != mango.begin()) {
            Min = min(Min, abs(*(--it) + delta));
        }

        cout << Min << "\n";

        it = mango.lower_bound(calc(i));

        if (it != mango.end()) mango.erase(it);
        mango.insert(calc(i) - n);

        // cout << "del " << calc(i) + delta << "\n";
        // cout << "add " << calc(i) - n + delta + 1 << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // init();
    int T = 1;
    // cin >> T;
    while (T--) sol();
    return 0;
}