A. X 轴 详细题解

题目重述

在 $X$ 轴上给定三个整数点 $x_1, x_2, x_3$（$1 \le x_i \le 10$）。你可以选择一个整数坐标点 $a$（可以与给定点重合），定义总距离 $f(a) = |x_1 - a| + |x_2 - a| + |x_3 - a|$。求 $f(a)$ 的最小值。

核心思路

对于一维数轴上的多个点，到这些点的距离之和最小的点就是这些点的中位数。当点的个数为奇数时，中位数是唯一的（排序后中间那个数）；当为偶数时，任何介于中间两个数之间的点都能得到相同的最小和。本题中 $3$ 个点，因此最优的 $a$ 就是三个点的中位数。

理由

• 绝对值函数 $|x - p|$ 是凸函数，多个凸函数的和仍是凸函数，最小值在导数符号变化处取得。对于离散整数点，最小值出现在排序后的中间位置。
• 更直观地：考虑数轴上的点，将 $a$ 从 $-\infty$ 向右移动，每经过一个点，该点对总距离的贡献从递减变为递增。总距离的斜率等于（左边点的个数减去右边点的个数）。当 $a$ 位于中位数时，左边和右边点的个数相等（或差 $1$），此时斜率为 $0$（或从负变正），达到最小值。

算法步骤

1. 读入 $t$ 个测试用例。
2. 对每个测试用例，读入三个整数 $x_1, x_2, x_3$。
3. 将三个数排序，取出中间的那个数（即排序后的第二个元素）作为 $median$。
4. 计算 $ans = |x_1 - median| + |x_2 - median| + |x_3 - median|$。
5. 输出 $ans$。

时间复杂度

每个测试用例只需常数时间，$t \le 1000$，总复杂度 $O(t)$，非常快。

正确性证明

设排序后的三个数为 $x_{(1)} \le x_{(2)} \le x_{(3)}$。对于任意 $a$，总距离 $f(a)$ 的函数图像是分段线性凸函数，最小值在 $a = x_{(2)}$ 处取得。因为当 $a < x_{(2)}$ 时，其左边有 $1$ 个点（$x_{(1)}$），右边有 $2$ 个点（$x_{(2)}$ 和 $x_{(3)}$），导致斜率为 $1 - 2 = -1$（实际上导数为负），函数递减；当 $a > x_{(2)}$ 时，左边有 $2$ 个点，右边有 $1$ 个点，斜率为 $2 - 1 = 1$（导数为正），函数递增。所以 $a = x_{(2)}$ 是唯一的极小值点。因此，中位数即为最优解。

示例验证

• 输入 1 1 1：排序为 $[1,1,1]$，中位数 $1$，$f(1)=0$。
• 输入 1 5 9：排序 $[1,5,9]$，中位数 $5$，$f(5)=4+0+4=8$。
• 输入 8 2 8：排序 $[2,8,8]$，中位数 $8$，$f(8)=0+6+0=6$。
• 输入 10 9 3：排序 $[3,9,10]$，中位数 $9$，$f(9)=1+0+6=7$。 与样例输出一致。

总结

本题是一维曼哈顿距离极小化问题，直接取中位数即可。由于数据范围极小，也可以暴力枚举 $a$ 从 $1$ 到 $10$ 求解，但利用中位数是最简洁的解法。注意本题的坐标范围很小，但原理适用于任意大小的整数。