题解：P12890 [蓝桥杯 2025 国 Java B] 道具摆放

littlesnake · 2025-12-05 17:32:11 · 题解

我们先考虑最优方案，最优方案交换次数就是逆序对个数。不难想到可以使用树状数组或者归并排序实现。随后我们增加步数，凑出 m 的倍数。

我们有任意 x,y，可以把 x 和 y 交换两次，等同于没有交换，所以只要最优方案和任意一个 m 的倍数奇偶性相同，就成立。

当最优方案和 m 都是奇数或者偶数，必然成立。当最优方案为偶数，m 为奇数也可以成立。如：最优方案为 6，m 为 5，那么只需要增加 4 步就可以到 10（5 的倍数）。

最后与结果有关的 m 的倍数最多只有两个，分别判断一下即可，注意特判一下最优方案为 0 的情况。

这里我用了树状数组实现逆序对求解，ans 是最优方案。

代码：

# include <bits/stdc++.h>
# define ll long long
# define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

const ll N = 1e5 + 5;
ll a[N], tr[N];
ll n, m, ans;

ll lowbit (ll x) { return x & -x; }

void update (ll x, ll y) {
    for (ll i = x; i <= n; i += lowbit (i))
        tr[i] += y;
}

ll query (ll x) {
    ll res = 0;
    for (ll i = x; i; i -= lowbit (i))
        res += tr[i];
    return res;
}

int main () {

    ios::sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n >> m;
    for (ll i = 1; i <= n; i ++) {
        cin >> a[i];
        ans += (i - 1) - query (a[i]);
        update (a[i], 1);
    }
    ll x = (ans - 1) / m + 1;
    if (ans == 0) cout << 0;
    else if (ans % 2 == 1 && m % 2 == 0) cout << -1;
    else if ((ans % 2) == ((x * m) % 2)) cout << x * m;
    else if ((ans % 2) == ((x * m + m) % 2)) cout << x * m + m;

    return 0;
}