自动搬运

查看原文

来自洛谷，原作者为

	Iggle_Piggle c 2 h 5 o h || 小六蒟蒻 || 蓝名壶关

搬运于2025-08-24 21:27:24，当前版本为作者最后更新于2024-01-17 16:58:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题传

这是一道贪心题。

从起点到终点和从终点到起点是等效的，所以视两者为端点。

设端点 $s,t$ 且 $s<t$，传送门 $p_1,p_2$ 且 $p_1<p_2$。

不妨求从 $s$ 至 $t$ 的最短距离。

设想，若要使用传送门，则一定是从 $p_1$ 到 $p_2$ 的。

采用反证法，假设 $p_2$ 至 $p_1$ 使用传送门。

因为 $s$ 到 $t$ 是向左走，而 $p_2$ 至 $p_1$ 是向右走，所以这样使用传送门一定产生多余的步数。

所以，若要使用传送门，则一定是从 $s$ 至 $p_1$ 再到 $p_2$ 最后到 $t$。

最后我们算答案就从用传送门和不用传送门中，花费距离取最小即可，也即

#include<bits/stdc++.h>
using namespace std;
int a, b, c, d;
signed main()
{
	scanf("%d%d%d%d", &a, &b, &c, &d);
	if(a > b) a ^= b ^= a ^= b;
	if(c > d) c ^= d ^= c ^= d;
	printf("%d", min(b - a, abs(c - a) + abs(d - b)));
	return 0;
}