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

· · 题解

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

前置芝士：逆序对求解方法。\ 不会的先去这里。

题意

给一个 1,2,\dots,n 的排列，交换 m 的倍数次使升序数列变成它，问至少需要交换多少次，如果不可能则输出 -1。

思路

相当于将排列变成升序。

每交换一次就会至多减少一个逆序对，所以至少需要交换的次数为逆序对数量，可以使用树状数组或归并排序来实现。我这里使用好写的树状数组。

求出逆序对数量 cnt 后，可以求出 f ，至少需要 f\cdot m 次交换。\ 可以通过一直交换两个数来增加次数，而且很好证明增加的次数一定为偶数。\ 分个类：

然后呢？没了？确实。

代码

清晰的思路，简洁的树状数组。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[500010],c[500010];
int cnt;
int lowbit(int x){return x&(-x);}
int que(int x){int re=0;while(x>0)re+=c[x],x-=lowbit(x);return re;}
void upd(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=n;i;i--) cnt+=que(a[i]-1),upd(a[i],1);
    int f=(cnt+m-1)/m;
    if(f*m%2==cnt%2) printf("%lld",f*m);
    else if((f+1)*m%2==cnt%2) printf("%lld",(f+1)*m);
    else printf("-1");
}