自动搬运

查看原文

来自洛谷，原作者为

	Nahida_Official 【現役】クサナリちゃんは、頑張っているすべてのOIerを応援していますね〜

搬运于2025-08-24 23:07:35，当前版本为作者最后更新于2024-12-26 15:38:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

通过描述和所给例子不难发现，当队列中有 $n$ 个队员时，无论开始状态是向左还是向右传，在经过 $n$ 次传球后，队列会进行反转。

举例如下：

输入：
7
7 0 1
7 0 2
7 0 3
7 0 4
7 0 5
7 0 6
7 0 7
输出：
4 1 2 3 5 6 7 
4 1 2 5 6 7 3 
5 4 1 2 6 7 3 
5 4 1 6 7 3 2 
6 5 4 1 7 3 2 
6 5 4 7 3 2 1 
7 6 5 4 3 2 1

输入:
7
7 1 1
7 1 2
7 1 3
7 1 4
7 1 5
7 1 6
7 1 7
输出：
1 2 3 5 6 7 4 
5 1 2 3 6 7 4 
5 1 2 6 7 4 3 
6 5 1 2 7 4 3 
6 5 1 7 4 3 2 
7 6 5 1 4 3 2 
7 6 5 4 3 2 1 

所以在经过 $2 \times n$ 次传球后，队列就会回到初始状态。

由此可以想到将操作次数 $k \bmod 2 \times n$ 之后进行模拟。

思路 1：

建立一个数组模拟操作，每次操作之后对数组进行更新，但由于更新数组需要双层循环，在题目条件 $3 \le n \le 2\times 10^5$ 限制下会 TLE。

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MANX=1e6;
ll T,n,x,k,mid;
int a[MANX];
void change(){
	if(x==0){
		int y=a[mid];
		a[0]=y;
		for(int i=mid-1;i>=0;i--){
			a[i+1]=a[i];
		}
		x=1;
	}else if(x==1){
		int z=a[mid];
		a[n+1]=z;
		for(int i=mid;i<=n+1;i++){
			a[i]=a[i+1];
		}
		x=0;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n>>x>>k;
		k%=2*n;
		for(int i=1;i<=n;i++){
			a[i]=i;
		}
		mid=(1+n)/2;
		for(int i=1;i<=k;i++){
			change();
		}
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}

Record

既然数组暴力不可取，那么转换思路。

思路 2：

开两个双端队列，分别记录中间队员的左边和右边，而中间队员新建一个变量 $mid$ 存储。

根据题目样例解释：

第 0 次传球后 : 1 2 3 （接下来 2 号球员向左传球）
第 1 次传球后 : 2 1 3 （接下来 1 号球员向右传球）
第 2 次传球后 : 2 3 1 （接下来 3 号球员向左传球）
第 3 次传球后 : 3 2 1

不难发现，当中间队员向左传球时，将中间队员压入左边队列的头部，并且将中间队员 $mid$ 设置为左边队列的尾部并弹出；而向右方传球则将中间队员压入右边队列的尾部，并且将中间队员 $mid$ 设置为右边队列的头部并弹出。

对队列操作不需要额外循环，单层循环即可。

另外需要注意的点：

• 记得转移状态（更新 $x$）。

• 在读入数据的时候记得两个队列都要从尾部压入数据，否则会导致原队列乱序而得不出正确答案。

• 别忘记输出 $mid$。

• 记得开 long long。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MANX=1e6;
ll T,n,x,k,num;
deque<ll> a,b;
ll mid;
void change(){
	if(x==0){
		a.push_front(mid);
		mid=a.back();
		a.pop_back();
		x=1;
	}
	else if(x==1){
		b.push_back(mid);
		mid=b.front();
		b.pop_front();
		x=0;
	}
}//模拟 
void print(){
	for(int i=1;i<=num;i++){
		cout<<a.front()<<" ";
		a.pop_front();
	}
	cout<<mid<<" ";
	for(int i=1;i<=num;i++){
		cout<<b.front()<<" ";
		b.pop_front();
	}
	cout<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	//freopen("2.in","r",stdin);
	//freopen("2.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>x>>k;
		k%=(2*n);//取模 
		num=(n+1)/2-1;//左右队列的长度 
		for(int i=1;i<=num;i++){
			a.push_back(i);
		}
		mid=(n+1)/2;
		for(int i=mid+1;i<=n;i++){
			b.push_back(i);
		}
		for(int i=1;i<=k;i++){
			change();
		}
		print();
	}
	return 0;
}

AC Record