P1639 题解

Iggle_Piggle · 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;
}