Moe's CF Life

喵~ 主人，你好呀！今天我们来看一道简单又有趣的题目：A. Letter Home。这道题就像是计划一次完美的散步路线，要用最少的步数拜访所有指定的小窝，感觉很有趣呢，的说！

题目大意

想象一下，我们正站在一根无限长的数轴上，就像猫猫在屋顶的横梁上散步一样，喵~

我们有一个初始位置 s。
有一份清单，上面写着 n 个我们必须拜访的坐标点 x_1, x_2, ... , x_n。
我们每次只能向左或向右移动一个单位的距离。
我们的任务是：找到一条路线，从 s 出发，访问到所有清单上的坐标点，并且总步数最少。

注意哦，我们一开始就在 s 点，所以 s 点就算是被访问过啦。

题解方法

要解决这个问题，我们得像聪明的猫猫一样思考，找到最省力气的路线，的说！

首先，我们来分析一下任务。我们需要访问所有在清单 x 上的点。但是，我们一开始就在 s 点了，如果清单上的某个点正好就是 s，那我们岂不是已经完成任务了？对啦！所以，我们可以先把所有等于 s 的点从清单上划掉，因为我们已经身处此地，不用再特地跑一趟了，喵~

现在，我们的清单上只剩下那些不等于 s 的、真正需要我们动身去访问的点了。我们把这些点称为“目标点”。

最简单的情况：如果划掉 s 之后，清单变空了，说明所有需要访问的点就是我们脚下的 s 点。那我们一步都不用动啦！答案就是 0。
一般情况：如果清单上还有目标点，我们该怎么走呢？因为所有点都在一条直线上，要访问所有目标点，我们的路径必须覆盖从“最左边的目标点”到“最右边的目标点”之间的所有区域。不然的话，肯定会漏掉一些在中间的点，对吧？
- 设 min_target 是所有目标点中坐标最小的那个。
- 设 max_target 是所有目标点中坐标最大的那个。
要访问所有目标点，我们至少要走完 min_target 到 max_target 这一段路。这段路的长度是 max_target - min_target。
那么，从起点 s 出发，我们怎么走最划算呢？其实只有两种最直接、最聪明的选择，喵~
- 策略一：先去左边！ 从 s 出发，先走到最左边的目标点 min_target，然后再从 min_target 一路向右，走到最右边的目标点 max_target。
  - 总步数 = (从 s 到 min_target 的步数) + (从 min_target 到 max_target 的步数)
  - 也就是 abs(s - min_target) + (max_target - min_target)。
- 策略二：先去右边！ 从 s 出发，先走到最右边的目标点 max_target，然后再从 max_target 一路向左，走到最左边的目标点 min_target。
  - 总步数 = (从 s 到 max_target 的步数) + (从 max_target 到 min_target 的步数)
  - 也就是 abs(s - max_target) + (max_target - min_target)。
任何其他绕来绕去的走法，都只会增加不必要的路程。所以，我们只要计算出这两种策略各自需要多少步，然后取那个更小的数字，就是我们的最终答案啦！是不是很简单呀，喵？

题解

下面我们来看看代码是怎么实现这个思路的，的说。

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 这个函数用来解决单个测试用例
void solve() {
    int n;
    int s;
    std::cin >> n >> s;
    
    // 我们创建一个小本本 `targets_to_visit`，
    // 用来记下那些我们还没去过的、需要拜访的地方。
    std::vector<int> targets_to_visit;
    for (int i = 0; i < n; ++i) {
        int xi;
        std::cin >> xi;
        if (xi != s) {
            targets_to_visit.push_back(xi);
        }
    }

    // 如果小本本是空的，说明我们哪儿也不用去，原地待着就好啦。
    // 所以步数是 0，喵~
    if (targets_to_visit.empty()) {
        std::cout << 0 << "\n";
        return;
    }

    // 题目保证了输入的 x 数组是排好序的，
    // 所以我们过滤后的 `targets_to_visit` 也是有序的。
    // 第一个元素就是要去的点里最左边的（min_target）。
    int min_target = targets_to_visit.front();
    // 最后一个元素就是最右边的（max_target）。
    int max_target = targets_to_visit.back();

    // 计算策略一的代价：先去最左边的点，再走到最右边。
    int cost_via_min_first = std::abs(s - min_target) + (max_target - min_target);
    
    // 计算策略二的代价：先去最右边的点，再走到最左边。
    int cost_via_max_first = std::abs(s - max_target) + (max_target - min_target);

    // 最后，比较一下两种方案的代价，选一个最小的输出就好啦！
    std::cout << std::min(cost_via_min_first, cost_via_max_first) << "\n";
}

int main() {
    // 快速输入输出，让程序跑得快一点点
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但也涉及了一些有用的编程小知识哦，喵~

贪心算法 (Greedy Algorithm) 这个问题的核心思想其实是一种叫做“贪心算法”的东西。贪心算法的意思是，在每一步选择中，都采取当前状态下最好或最优的选择，从而希望能导致全局最好或最优的结果。在这道题里，我们的“贪心”选择体现在：我们不去考虑那些复杂的、来回折返的路线，而是直接构造出两条最直接的路线（先左后右 vs 先右后左），然后在这两条局部最优的路线中选择一个全局最优的。对于这类简单路径问题，这种贪心策略是完全正确的！
构造性算法 (Constructive Algorithm) 我们的解法不是通过搜索所有可能的路径来找到最短的，而是直接“构造”出了最优路径的候选方案。这种直接构建解决方案的方法，就叫做构造性算法。当问题结构比较清晰时，构造法通常比暴力搜索要高效得多。
绝对值 abs() 在数轴上计算两点之间的距离，我们用的是 abs(a - b)。abs() 函数会返回一个数的绝对值，确保我们得到的距离永远是正数或零。这是计算一维空间距离的基础，非常常用哦。

好啦，这次的题解就到这里啦！希望对主人有所帮助，喵~ 如果还有其他问题，随时可以再来找我哦！

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍