P7818排列

· · 题解

这是我的第一篇题解。感谢@vectorwyx大佬不吝赐教。

题意为求将一个给定的全排列交换相邻的数 k 次后能得到的字典序最小的全排列。

既然要求字典序最小，那么一定要靠前的数尽量小，我们就想到了贪心算法：

设当前操作到了第 i 位，剩余交换次数 k'。每次查找能够交换到第 x 位的数中最小的数，将其交换到第 i 位，再将 k' 减去相应的交换次数。

具体地说，我们用树状数组维护原序列第 1 位至第 i 位未被选的数的个数 (x\in[1,n])，用线段树维护原序列第 l 位至第 r 位未被选的数中的最小值及其位置 (l,r\in[1,n])。

每次操作，如果所有未选过的数都能交换到第 i 位，我们就找 [1,n] 中的未选的最小值 x ；否则，通过二分查找确定第 k' 个未选的数的位置，找 [1,x+k'+1] 中未选的最小值 x。将 x 交换到第 i 位（这里我们将其压入队列 ans,标记 x 为已经选过，并不进行实际交换），k' 减去交换次数。如果 k'=0 或者所有数都确定好位置，就结束交换。

最多进行 n 次操作，每次操作二分查找 + 树状数组的时间复杂度为 O(\log^2 n)，交换时线段树和树状数组的更新时间复杂度为 O(\log n)，总时间复杂度为 O(n\log^2 n)。

但是这样交上去，我们却发现 WA 了 5 个点。为什么？因为我们没有注意到恰好 k 次（不是最多 k 次）！如果排完后还有多余次数 k'',若 k'' 为偶数则不用管，如果 k'' 是奇数，那么交换最后两个数字。

显然如果次数多余，当前的全排列一定已经是递增的。如果剩余偶数次，交换最后两位 k'' 次后不变；如果是奇数次，那么交换后等价于交换最后两位一次。这样可以确保字典序最小。

AC code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define ll long long
using namespace std;
const int N=4e6+5,INF=0x3f3f3f3f;
ll n,k,a[N],bk[N],pos,tot,ans[N];
struct xxs{
    ll p,num;
}x;
namespace BIT{
    ll c[N];
    void add(int x,ll k){
        while(x<=n){
            c[x]+=k;
            x+=x&-x;
        }
    }
    ll search(int x){
        ll ans=0;
        while(x){
            ans+=c[x]; 
            x-=x&-x;
        }
        return ans;
    }
}

int half(int lim){
    int mid,l=1,r=n+1;
    while(l<r){
        mid=(l+r)>>1;
        if(BIT::search(mid)>=lim)
            r=mid;
        else
            l=mid+1;
    }
    return l;
}
namespace SGT{
    xxs c[N];
    int L[N],R[N];
    void pu(int rt){
        if(c[rt<<1].num<c[rt<<1|1].num)
            c[rt]=c[rt<<1];
        else
            c[rt]=c[rt<<1|1];
    }
    void build(int l,int r,int rt){
        L[rt]=l,R[rt]=r;
        if(l==r){
            c[rt]=(xxs){l,a[l]};
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        pu(rt); 
    }
    void upd(int x,ll k,int rt){
        if(L[rt]>x||R[rt]<x)
            return;
        if(L[rt]==R[rt]){
            c[rt].num=k;
            return;
        }
        upd(x,k,rt<<1);
        upd(x,k,rt<<1|1);
        pu(rt);
    }
    xxs qry(int l,int r,int rt){
        if(L[rt]>r||R[rt]<l)
            return (xxs){1,INF};
        if(L[rt]>=l&&R[rt]<=r)
            return c[rt];
        xxs lx=qry(l,r,rt<<1);
        xxs rx=qry(l,r,rt<<1|1);
        return (lx.num<rx.num?lx:rx);   
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        bk[i]=1;
        BIT::add(i,1);
    }
    SGT::build(1,n,1);//维护区间最小值及其初始位置 
    for(int xx=1;xx<=n&&k;xx++){
        if(k<n-xx)
            pos=half(k+1); 
        else
            pos=n;
        x=SGT::qry(1,pos,1);

        k-=BIT::search(x.p)-1;//交换次数=当前为序列中未选的第几个数-1
        ans[++tot]=x.num;

        //标记为已选
        bk[x.p]=0;
        BIT::add(x.p,-1);
        SGT::upd(x.p,INF,1);
    }

    if(k&& k&1)swap(ans[n-1],ans[n]);

    if(tot<n)//未被选的依次排到队尾
        for(int i=1;i<=n;i++)
            if(bk[i])
                ans[++tot]=a[i];

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}

The End.