自动搬运

查看原文

来自洛谷，原作者为

	FreeTimeLove fAiry tales oF yesterday will grOw but never die

搬运于2025-08-24 22:33:22，当前版本为作者最后更新于2021-10-24 22:08:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是我的第一篇题解。感谢@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.