1 条题解

  • 0
    @ 2026-9-23 18:02:07

    以下称 11 到 nn 在同一个块,n+1n + 1 到 2×n2 \times n 在同一个块,两个块不一样。

    对于一次临项交换只有两种情况要么在同一个块,要么在两个块的交界处。

    不难得出只要在一个块内有 11,那么逆序对就能变为任意值。

    接下来考虑在两个块的交界处。

    只会呈现两种形态 0101 状和 1010 状。 ::::info[0101 状分析] 对于左边的块:交换之后 11 在最后就没有什么作用了,设 ll 到 nn 都是 11,交换之后左边块内的逆序对数为 11 到 l−1l - 1 的逆序对数。

    对于右边的块:交换之后 00 就堆在最左边了,也没什么用,设 n+1n + 1 到 rr 都是 00,交换之后右边块内的逆序对数为 r+1r + 1 到 2×n2 \times n 的逆序对数。 :::: ::::info[1010 状分析] 对于左边的块:设交换之后 ll 到 nn 都是 00,那么逆序对数为 11 到 l−1l - 1 的逆序对数加上 (n−l+1)×∑i=1x−1ai(n - l + 1) \times \sum^{x - 1}_{i = 1} a_i。

    对于右边的块:设交换之后 n+1n + 1 到 rr 都是 11,那么逆序对数为 r+1r + 1 到 2×n2 \times n 的逆序对数加上 $[r - (n + 1) + 1] \times \sum^{2 \times n}_{i = r + 1} (1 - a_i)$。 :::: 由于进行一次 0101 状操作后再进行 1010 状操作等于没进行操作,显然无用,所以可以枚举两种操作的使用次数,然后再取最小值。

    #include<bits/stdc++.h>
    const int MAXN = 2e5 + 5;
    #define pb push_back
    typedef long long LL;
    const LL inf = 1e15;
    int n, a[2 * MAXN];
    std::vector<int> v[2][2];
    LL suf[MAXN][2], pre[MAXN][2];
    inline void init()
    {
        for(int i = n; i >= 1; i--)
        {
            v[0][a[i]].pb(i);
        }
        for(int i = n + 1; i <= 2 * n; i++)
        {
            v[1][a[i]].pb(i);
        }
        int c = 0, c1 = 0, c2 = 0;
        for(int i = 1; i <= n; i++)
        {
            if(a[i] == 1) c1++;
            else c += c1;
            suf[i][0] = c;
        }
        c = c1 = c2 = 0;
        for(int i = 2 * n; i >= n + 1; i--)
        {
            if(a[i] == 0) c2++;
            else c += c2;
            suf[i][1] = c;
        }
        c = 0;
        for(int i = 1; i <= n; i++)
        {
            if(a[i] == 1) c++;
            pre[i][0] = c;
        }
        c = 0;
        for(int i = 2 * n; i >= n + 1; i--)
        {
            if(!a[i]) c++;
            pre[i][1] = c;
        }
    }
    int main()
    {
        scanf("%d", &n);
        for(int i = 1; i <= 2 * n; i++)
        {
            scanf("%d", &a[i]);
        }
        init();
        LL ans = abs(suf[n][0] - suf[n + 1][1]), s = 0;
        for(int i = 0; i < std::min(v[0][0].size(), v[1][1].size()); i++)
        {
            int l = v[0][0][i], r = v[1][1][i];
            LL nl = suf[l - 1][0], nr = suf[r + 1][1];
            s += (n - l) + (r - (n + 1)) + 1;
            ans = std::min(ans, s + abs(nl - nr));
        }
        init(); s = 0;
        for(int i = 0; i < std::min(v[0][1].size(), v[1][0].size()); i++)
        {
            int l = v[0][1][i], r = v[1][0][i];
            LL nl = suf[l - 1][0] + 1LL * (n - l + 1) * pre[l - 1][0], nr = suf[r + 1][1] + 1LL * (r - (n + 1) + 1) * pre[r + 1][1];
            s += (n - l) + (r - (n + 1)) + 1;
            ans = std::min(ans, s + abs(nl - nr));
        }
        printf("%lld\n", ans);
        return 0;
    }
    
    • 1

    信息

    ID
    6947
    时间
    2000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    36
    已通过
    7
    上传者