B4239 [海淀区小学组 2025] 拜访朋友

chen_zhe · 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;