自动搬运

查看原文

来自洛谷，原作者为

	聊机 梦开始的地方

搬运于2025-08-24 22:48:30，当前版本为作者最后更新于2023-07-16 16:54:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

在高铁上过掉了这个题，因为没看到有人写题解，所以来填补一下空白。

做法：归并排序+卡常

首先数据范围要求我们用 $\log$ 级的算法来解决这道题目，很显然的想到归并排序，可是当我细写的时候就发现并没有“排序套皮”这么简单。

$n$ 的范围是 $4\times10^4$，而操作次数要求我们 $10^6$ 以内，这就要求我们常数要在 $1.5$ 倍以内，这对我这种弱鸡来说是非常困难的，如果我们按照归并的常规思路来思考，每次分成两半，我们为给下半部分排序，一定要把上半部分扔出去，这是 $0.5$ 倍的常数，然后分开排好序以后，把这两半合到一起的时候需要 $1$ 倍的常数，把它们合到新的柱子上以后，再一起扔回原来的柱子，又需要 $1$ 倍的常数，总计是 $2.5$ 倍，这样我们保证了递归的每一层都是相同的大小顺序，但是常数太大。

我们需要把刚才的最后一次合并剪掉，这样常数才能满足要求。

如果我们不进行最后一次合并，那就说明我们进行排序完以后的这一段不在原本的柱子上，那你一开始分开的那两段排序完以后也不会在原本的柱子上，我们需要保证它们不会重叠在一起，所以我们需要规定一下让这两段排序完以后都去到哪个柱子，我们设当前这一段所在的柱子是 $p$，要去 $to$ 柱子，我们一开始要把前半段扔到 $to$ 柱子上，然后让后半段合并到 $3-p-to$ (就是另外一根柱子上），再让扔出去的前半段合并到 $p$ 柱子上，最后我们再把这两段合并到 $to$ 柱子上。我们还要注意的是，因为我们只进行了一次合并，所以顺序会颠倒，我们需要让每相邻的两层的排序方式相反。

AC code：

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+2;
int n,a[N];
int tot,a1[N*50],a2[N*50];
#define endl '\n'
#define move(a,b) a1[++tot]=a,a2[tot]=b
#define put(a,b) cout<<(char)('A'+a)<<' '<<(char)('A'+b)<<endl
inline bool comp(int o,int x,int y) {
	if(o) return x>=y;
	else return y>=x;
}
bool cmp(int x,int y) {
	return x>y;
}
void divid(int p,int l,int r,int to,int o) {//参数意义同分析
	if(l==r) {
		move(p,to);
		return ;
	}
	int mid=(l+r)>>1,p2=3-to-p;
	for(int i=l;i<=mid;i++) move(p,to);
	for(int i=l,j=mid;i<=j;i++,j--) swap(a[i],a[j]);//这个reserve千万不要忘记！
	divid(p,mid+1,r,p2,o^1);
	divid(to,l,mid,p,o^1);
	int i=l,j=mid+1;
	while(i<=mid&&j<=r) {
		if(comp(o,a[i],a[j])) move(p,to),++i;
		else move(p2,to),++j;
	}
	while(i<=mid) move(p,to),++i;
	while(j<=r) move(p2,to),++j;
	if(o) stable_sort(a+l,a+r+1);
	else stable_sort(a+l,a+r+1,cmp);
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	divid(0,1,n,2,1);
	cout<<tot<<endl;
	for(int i=1;i<=tot;i++) put(a1[i],a2[i]);		
	return 0;
} 

说实话卡常这一部分我想了很久，就从卡常这一点来说，我认为这还是一道很不错的构造题的。

题外话：建议管理更新一下提交记录，把弱化版的记录删除掉，这样我们才能看到更多关于这题更好的做法。