自动搬运

查看原文

来自洛谷，原作者为

	Tracy_Loght 爱与火的歌舞，命与情的交织，是遗憾的狂想最后一曲

搬运于2025-08-24 21:43:53，当前版本为作者最后更新于2024-12-06 15:00:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意：

求多点在三角字形塔中的距离。

分析：

找规律，如图：

（你看看我多好，还不点个赞）

有一个容易得到的结论:

比如我们要从 $6$，$6$ 走到 $4$ 行的任意一个位置，则一定可以用三到四步之间走到。

• $3$ 步：第二个坐标为奇数。

• $4$ 步：第二个坐标为偶数。

映射到所有的情况，从 $a$，$b$ 到 $x$，$y$ 且 $(a > x)$，则 $y$ 如果在区间 $[b - ( a - x ) \times 2，b]$ 内只需要 $( a - x ) \times 2$ 或 $( a - x ) \times 2 +1$ 次破壁，具体看奇偶性。

如果不在这个区间内呢？

答案是两点之间，直线最短，计算区间里目标的最短距离即可（直线上不需要说了吧）。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,s,x,y,jl=99999999;
long long mx,my;
int dpzc_jf(int a,int b,int x,int y){
	int l,r,p=(a-x)*2;
	if(b%2==1) {l=b-p;r=b;}
	else {l=(b+1)-p;p--;r=b-1;}
	if(l<=0) l=1; if(r>x*2-1) r=x*2-1;
	if(l<=y&&y<=r) return y%2==1?p:p+1;
	else if(y>r) return p+y-r;else return p+l-y;
}
int main(){
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0); 
	cin>>n>>m>>x>>y;
	while(m--){
		long long a,b,as;cin>>a>>b;
		if(a>x) as=dpzc_jf(a,b,x,y);
		else as=dpzc_jf(x,y,a,b);
		if(as+1<jl) mx=a,my=b;
		jl=min(jl,as+1);
	}
	cout<<mx<<" "<<my<<"\n";
	cout<<jl;
	return 0;
}