自动搬运

查看原文

来自洛谷，原作者为

	djh0314 我在时光斑驳深处，聆听到花开的声音。

搬运于2025-08-24 22:20:52，当前版本为作者最后更新于2023-08-11 21:45:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

洛谷。

题意

一共有 $n$ 个人，每个人有一个编号，编号为 $1\sim n$。原来有一个序列，问如何操作，使其变成指定序列。

每次操作，可以使编号为 $b$ 的人向前插队 $b$ 格。

（比较想知道为什么我们的翻译是青蛙）。

分析

这是一道构造题，我们需要使两个序列相近。

令原序列为 $A$，最后的序列为 $B$，我们定义一个中转的序列为 $C$，我们需要使 $A$ 先变成 $C$，再使 $B$ 倒退成 $C$。

对于这个 $C$ 序列，我们需要使他的性质要足够好，那么不妨令它是 1 直到 $n$。

我们在使序列接近我们的 $C$，我们就可以使我们匹配的顺序从小到大或者从大到小。

每次，我们使两个 $C$ 中相邻的数 $i$ 与 $i+1$ 相邻。

不妨令 $i$ 的位置在 $i+1$ 的左侧。（因为是个环，所以可以转化）。要使两个相邻，我们有两种操作。

1. 使 $i$ 移动到 $i+1$ 的左侧。
2. 使 $i$ 到 $i+1$ 中间的数都移动开。

对于第一种，我们可以在模拟的过程中发现，我们移动 $cnt$ 步实际上与移动 $cnt \bmod (n-1)$ 步是相同的。

也就是说，我们移动 $k$ 此后，使 $i$ 移动到 $i+1$ 左侧，需要 $k\times i \equiv x \pmod{n-1}$，（$x$ 为移动 $x$ 步可以使其相邻）。

这也就使得，我们这种移动方式可能不能仅靠移动 $i$ 使其相邻，我们需要再移动一些其他数，比较复杂，所以就不细节考虑。

对于第二种，我们贪心上可以从小到大移动这些数，是这些数移出这个区间内。

这时我们发现，我们的 $n-1$ 不论怎么移动都无法移动出我们的区间，于是，我们在枚举相邻的数时，需要从大到小。

稍微证明一下，假如我们的另一个区间的之间长度为 $D$，那么我们的两个之间的数的最小值最大也就是 $D+1$，但是我们的这一整个区间的长度是 $D+2$（包括 $i$ 与 $i+1$），那也就表示我们的这个点必然可以移动进这个区间。

然后我们就可以使我们的区间不断移动出这个区间了。

于是，我们就可以解决了从 $A$ 到 $C$ 的过程。

而我们从 $B$ 逆推回 $C$，我们只需要是我们移动的方式从顺时针变成逆时针，再反向输出即可。

inline int find(int a[],int x) {
	for(int i=1; i<=n; ++i) if(a[i]==x) return i;
}

inline bool check(int L,int R,int x) {
	if(L<R) return L<x&&x<R;
	else return x<R||L<x;
}

inline void solve(int a[],int to[],bool flag) {
	top=0;
	for(int i=n-1; i; --i) {
		while(1) {
			int L=find(a,i);
			int R=find(a,i+1);
			if(L%n+1==R) break;
			int idx=L%n+1;
			for(int j=L%n+1; j!=R; j=j%n+1) if(a[j]<a[idx]) idx=j;
			R=find(a,n);
			while(check(L,R,idx)) {
				ans[++top]=a[idx];
				int cnt=a[idx];
				while(cnt--) {
					swap(a[idx],a[to[idx]]);
					if(a[idx]==n) R=idx;
					else if(a[idx]==i) L=idx; 
					idx=to[idx];
				}
			}
		}
	}
	if(!flag) for(int i=1; i<=top; ++i) cout<<ans[i]<<"\n";
	else for(int i=top; i; --i) cout<<ans[i]<<"\n";
}

总结一下，我们解决这道题需要非常的思考力，（反正我不讲绝对做不出来）。