题解：轮回疯狂

K8He · 2024-09-26 17:08:53 · 题解

这里是 checker 题解。

赛后 UPD：虽然树状数组本来就是要放过去的但是你们怎么都写这个，急眼了。

首先我们知道只有一操作答案是逆序对数。

考虑二操作，注意到存在一种方案是将前 n - 1 个数都删了，所以答案不会超过 n - 1，进一步得知最优方案交换次数不超过 n - 1。

尝试利用这个上界做一些暴力。直接进行二操作的话，每次操作后序列的交换次数不增，没有什么好的性质。不过如果倒过来进行二操作，依次加当前还没有加的最大值（加入后是序列的最小值），每次操作后序列的交换次数是不降的，然后如果直接暴力插入排序求解，可以在交换次数超过 n - 1 后直接跳出，因为之后一定是更劣解。当然交换次数超过答案就跳了也对因为答案肯定不大于 n - 1。

时间复杂度是 O(n)，因为插入排序交换操作只会进行 O(n) 次。

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 1e5 + 10, P = 998244353;
namespace IO {
    int rnt () {
        int x = 0, w = 1; char c = getchar ();
        while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
        while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
        return x * w;
    }
}
namespace SOLVE {
    using namespace IO;
    int n, a[N], p[N], b[N], ans;
    void In () {
        n = rnt ();
        _for (i, 1, n) p[a[i] = rnt ()] = i;
        return;
    }
    void Solve () {
        ans = n;
        int S = 0, m = 0;
        for_ (i, n, 1) {
            b[++m] = p[i];
            for_ (j, m, 2) {
                if (b[j] < b[j - 1])
                    break;
                std::swap (b[j], b[j - 1]);
                ++S;
            }
            if (S > n) break;
            ans = std::min (ans, S + i - 1);
        }
        return;
    }
    void Out () {
        printf ("%d\n", ans);
        return;
    }
}
int main () {
#ifndef ONLINE_JUDGE
    freopen ("data.in", "r", stdin);
    // freopen ("data.out", "w", stdout);
#endif
    SOLVE::In ();
    SOLVE::Solve ();
    SOLVE::Out ();
    return 0;
} /*

*/