自动搬运

查看原文

来自洛谷，原作者为

	N_Position WhileTrueRP++ // AFO.

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

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

以下是正文

题目翻译

在一个 $n\times n$ 的地图中，每个位置都有一只袋鼠，每次操作可以使每只袋鼠整体向上下左右四个方向移动一格，袋鼠不会超出地图范围，问：如何在 $3\times(n-1)$ 步及内将所有袋鼠移动到给定位置。

题目分析

共分为两个过程：汇集和移动到终点。

考虑汇集，显然只要所有袋鼠都在地图角落，便可汇集。

四个角中，显然要选取距离终点最近的。

最后只需要移到终点即可。

最会情况下移动到一个角上需要 $2\times(n-1)$ 次，移动到终点最多需要 $n-1$ 次，符合题意。

代码实现

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	if(a <= n/2){
		for(int i=1;i<n;i++){
			printf("U");
		}
		for(int i=1;i<a;i++){
			printf("D");
		}
	}else{
		for(int i=1;i<n;i++){
			printf("D");
		}
		for(int i=1;i<n-a+1;i++){
			printf("U");
		}
	}
	if(b <= n/2){
		for(int i=1;i<n;i++){
			printf("L");
		}
		for(int i=1;i<b;i++){
			printf("R");
		}
	}else{
		for(int i=1;i<n;i++){
			printf("R");
		}
		for(int i=1;i<n-b+1;i++){
			printf("L");
		}
	}
}