自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:18:03，当前版本为作者最后更新于2025-03-11 10:34:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

本题考察贪心。

首先特判特殊情况，当 $n=1$ 的时候，答案必然为 $0$。对于其他的情况，不妨先将读入的住所的坐标 $x_i$ 进行排序，使得 $x_1\leq x_2\leq x_3\leq \dots \leq x_n$，以便我们做后续处理。

陶陶拜访好朋友的移动轨迹一定是形如这两根黄色曲线，即：先走到一端再调头，拜访初始位置另外一侧的住所。因此，这里会出现两种情况，需要分类讨论。

假设一开始是向右走的，那么又会有两种情况。第一种情况是选择拜访 $x_1,x_2,\dots,x_{n-1}$ 这些住所，另外一种情况是拜访 $x_2,x_3,\dots,x_n$ 这些住所。这里也需要进行分类讨论，判断哪一种路线更近。对于前者情况，其所需走的距离是 $|x_0-x_{n-1}|+|x_{n-1}+x_1|$，后者情况所需走的距离是 $|x_0-x_n|+|x_n-x_2|$，两者取其低即可。

一开始向左走的情况也同理，也需要分成两种情况进行分类讨论。最后取得距离最短值即可。这一部分的参考代码如下：

long long ans1 = min(abs(x[n] - x0) + abs(x[n] - x[2]), 
                     abs(x[n - 1] - x0) + abs(x[n - 1] - x[1])); // 一开始向右走
long long ans2 = min(abs(x[1] - x0) + abs(x[1] - x[n - 1]),
                     abs(x[2] - x0) + abs(x[n] - x[2])); // 一开始向左走
cout << min(ans1, ans2) << endl;