三个有序数组找最小距离：从固定 b 到线性扫描

三个有序数组找最小距离：从固定 b 到线性扫描

我最开始做到这道题时，题面里的距离只有两项。后来才发现，它并不是原始 408 题目的正确距离定义。

但这个错误版本本身仍是一个完整的问题，而且从它走到正确版本，能看清楚：目标函数只多一项，算法为什么会改变。

这一篇先把两项距离的问题讲明白：

三个数组非空、按非递减顺序排列，允许重复元素。目标是找出最小距离及任意一组达到它的元素。

1. 我的切入点：先把 b 定下来

我看到式子之后，第一反应是：a只和b有关，c也只和b有关，a和c之间没有直接的一项。

所以先固定b。此时挑a不会限制挑c，两个选择可以独立完成：

这个等号可以从两方面理解：任意组合都不可能小于右边两个最小值之和；分别选到两个最小值，又确实能组成一组合法答案。

比如A=[1,4,8]、B=[5,10]、C=[2,6,12]：

枚举B的所有元素，就不会漏掉最优组合中的b。此时根本不用同时枚举a、b、c。

2. 第一个正确解，再利用有序性

记三个数组的长度分别为 n=|A|、m=|B|、k=|C|。如果每次固定 b，都扫描 A 和 C，复杂度是 O(m(n+k))。

数组有序后，可以二分找第一个大于等于b的位置p。最近值只可能出现在p和p-1：左边越往左越远，右边越往右越远。p在数组两端时，仅检查存在的候选。

复杂度中写log(n+1)，是为了连长度为1的情况也能明确包含常数开销。

3. B也有序：上一次的位置还能用

如果b按照从小到大的顺序出现，A中最靠右的最近点位置不会往左走。C同理。

对两个不同的值x<y，y不比x远，当且仅当：

随着b增大，一旦y已经不比x远，这个关系就不会反转。如果x=y，两个距离始终相等，可以直接选择右边的位置。

因此维护A的指针i、C的指针j，每次固定新的b，只需继续向右寻找最近点。

对固定b，有序数组的距离先不增、后不减。跳过相等距离，再在下一项严格变远时停下，就找到最靠右的最小值。不会出现“先严格变远，后面又更近”的情况。

4. 原来写的严格小于，为什么需要修正

最初的伪代码用的是：

只有下一项距离严格更小，才让指针右移。

但数组可能有重复元素：

A = [1, 1, 4]
B = [4]
C = [4]

从A[0]开始，下一项还是1，距离没有严格减小，指针就停住了。算出的距离是3，实际最小值是0。

所以判断应当使用<=。它既跨过重复元素，也统一采用最靠右的最近点，方便复用到下一个b。

把原来的错误判断与这个反例放在一起看。图里的红色圈线只标两个点：严格 < 停在哪里，以及改成 <= 后怎样跨过两个 1。

这里不是“相等一定更优”，而是“相等时不能据此断言后面不会更近”。先跨过等距元素，再由下一项是否变远决定停止。

5. 完整 C 实现：输出距离，也保存所选元素

先约定本地测试的输入：每组依次给出 n m k，以及 A、B、C 的元素；可以连续输入多组，读取到 EOF。数组非空且非递减，允许重复值。每组输出 D a b c，有多个最优组合时任意一个都可以。

本地程序约定 1≤n,m,k≤200000，元素范围为 [-2147483648,2147483647]。这是验证工具的输入范围，不是原试卷的要求；超出约定范围的数据不用于这份程序的正确性结论。

输入：
3 2 3
1 4 8
5 10
2 6 12

一种输出：
2 4 5 6

下面是实际参与本地验证的完整 C11 程序：

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
int64_t distance;
int32_t a, b, c;
} Answer;

static int64_t distance_between(int32_t x, int32_t y) {
int64_t delta = (int64_t)x – (int64_t)y;
return delta >= 0 ? delta : -delta;
}

static Answer solve(const int32_t *a, size_t n,
const int32_t *b, size_t m,
const int32_t *c, size_t k) {
size_t i = 0, j = 0;
Answer best = {INT64_MAX, 0, 0, 0};
for (size_t t = 0; t < m; ++t) {
/* Advance through ties, including duplicate elements. */
while (i + 1 < n &&
distance_between(a[i + 1], b[t]) <= distance_between(a[i], b[t])) {
++i;
}
while (j + 1 < k &&
distance_between(c[j + 1], b[t]) <= distance_between(c[j], b[t])) {
++j;
}
int64_t d = distance_between(a[i], b[t]) + distance_between(b[t], c[j]);
if (d < best.distance) best = (Answer){d, a[i], b[t], c[j]};
}
return best;
}

static int read_array(int32_t *values, size_t length) {
for (size_t i = 0; i < length; ++i) {
if (scanf("%" SCNd32, &values[i]) != 1) return 0;
if (i > 0 && values[i] < values[i – 1]) return 0;
}
return 1;
}

int main(void) {
size_t n, m, k;
int count;
/* A single case is valid; repeated cases support local batch checking. */
while ((count = scanf("%zu%zu%zu", &n, &m, &k)) != EOF) {
if (count != 3 || n == 0 || m == 0 || k == 0 ||
n > 200000 || m > 200000 || k > 200000) return 1;
int32_t *a = malloc(n * sizeof(*a));
int32_t *b = malloc(m * sizeof(*b));
int32_t *c = malloc(k * sizeof(*c));
if (a == NULL || b == NULL || c == NULL) {
free(a); free(b); free(c);
return 1;
}
if (!read_array(a, n) || !read_array(b, m) || !read_array(c, k)) {
free(a); free(b); free(c);
return 1;
}
Answer result = solve(a, n, b, m, c, k);
printf("%" PRId64 " %" PRId32 " %" PRId32 " %" PRId32 "\\n",
result.distance, result.a, result.b, result.c);
free(a); free(b); free(c);
}
return 0;
}

这里不能先用 int 做减法，再把结果转成 64 位。例如 INT32_MAX-INT32_MIN 已经超出 32 位范围；必须在减法之前转换。

若元素为有符号 32 位整数，距离最大可达 8589934590：A 和 C 都选 2147483647，B 选 -2147483648。因此，元素使用 int32_t，距离使用 int64_t。

为什么程序分成这几个部分

算法不是一份必须靠输入输出才能调用的脚本。solve 只接收数组和长度，返回 Answer，不读输入、不打印结果；因此可以单独观察它的指针状态，也能在测试时直接替换另一种算法。

Answer 除了距离，还保存三元组。这既回应了“找一组元素”的题目要求，也让验证器能检查：输出的答案是否真的由合法元素产生。

注意 solve 的 O(1) 额外空间不包括调用者已经存下来的输入数组。程序结构分开之后，这两个空间开销也更容易讲清楚。

6. 为什么结果一定最优，为什么总时间是线性

每次处理b时，两根指针分别指向A、C中最靠右的最近点。第一次从数组开头寻找；后续因为最近位置不回退，可以从上次位置继续寻找。距离的先不增后不减性质保证扫描停止的位置就是最近点。

固定b的两个独立最小值之和，就是该b能得到的最小距离。把B中的所有b处理完并取最小值，就得到全局最优答案。

尽管for里还有while，两个指针都不回退：i最多前进n-1次，j最多前进k-1次，B遍历m次。每次成功推进与每轮末尾的一次失败判断加起来，仍是O(n+m+k)。

求解函数只使用指针和一组答案，额外空间O(1)。完整C程序存放输入数组的空间为O(n+m+k)，两者需要区分。

7. 没有现成判题站，怎样检查自己的算法

我给这道题配了本地判题器。小规模参考解直接枚举所有三元组，使用BigInt算距离，与单调指针完全独立。

判题也不只看一个预先写好的三元组，而是检查：

除了样例，还包含重复元素反例、负数、等距、整数极值，以及小值域完整穷举和固定种子的随机数据。

这里的“小值域完整穷举”有明确范围：元素取自 {-1,0,1}，长度为 1～3，列出所有非递减数组。三种长度分别有 3、6、10 个数组，共 19 个；A、B、C 任意组合，一共 19³=6859 组。它不是对任意整数、任意长度的穷举，但能系统覆盖短数组中的重复值、等距和大小关系。

还有几种可以交叉检查的性质：交换A和C不改变最优距离；往数组里加入已有值的副本不改变答案；三个数组同时加一个常数不改变答案；合法范围内同时乘正整数，距离应同比例增大。

大数据使用三数组共有元素的案例，能直接证明最小值为0。这里不会为了验证线性解，在200000元素规模上运行立方复杂度暴力。

测试是为了找反例和检查实现，正确性仍由上面的拆分与单调性证明支撑。这道题值得保留的推导顺序是：先固定b得到正确解，再利用数组有序做二分，最后发现查询也有序，让已有搜索结果服务于下一次查询。

这次实际运行的结果如下。两个批次有重复用例，不把它们相加当成不同用例数。

如果只想先复现最关键的检查，将前面的程序保存为 solution.c，使用支持 C11 的 GCC 编译：

gcc -std=c11 -O2 -Wall -Wextra solution.c -o solution

运行后输入重复元素反例：

3 1 1
1 1 4
4
4

正确输出是 0 4 4 4。把两个 while 中的 <= 改成 < 后，这个用例会输出 3 1 4 4。一个很小的反例，就能揭示大批随机测试未必碰得到的边界。

验证程序怎样设计，才不只是“运行一下看看”

求解程序要快，参考解要容易确认正确。小数据里，我选择直接枚举全部三元组，而不是再写一遍最近点算法，否则两份程序可能重复同一个错误。

下面摘出判题器核心计算的等价简化版本，使用 JavaScript 的 BigInt 避免参考解自己发生整数溢出。这是验证代码，不是替代前面的线性解：

const abs = x => x < 0n ? -x : x;
const distance = (a, b, c) => abs(a – b) + abs(b – c);

function bruteForce({ A, B, C }) {
let best = null;
for (const a of A) for (const b of B) for (const c of C) {
const d = distance(BigInt(a), BigInt(b), BigInt(c));
if (best === null || d < best) best = d;
}
return best;
}

function checkAnswer(test, line, expected) {
const fields = line.trim().split(/\\s+/);
if (fields.length !== 4 || fields.some(x => !/^-?\\d+$/.test(x))) return false;
const [d, a, b, c] = fields.map(BigInt);
const belongs = (xs, x) => xs.some(v => BigInt(v) === x);
return belongs(test.A, a) && belongs(test.B, b) && belongs(test.C, c)
&& d === distance(a, b, c) && d === expected;
}

const test = { A: [1, 1, 4], B: [4], C: [4] };
const expected = bruteForce(test);
console.log(String(expected)); // 0
console.log(checkAnswer(test, '0 4 4 4', expected)); // true
console.log(checkAnswer(test, '3 1 4 4', expected)); // false

这段代码可用 Node.js 运行。它只展示小数据参考解与答案检查，不包含完整的编译器调用、测试生成器和网页界面。不要在大数组上运行三重枚举。

完整工具把一次提交分成几个步骤：

参考解也有边界：完整工具只允许小数据进行暴力枚举，超过 2000000 个三元组时拒绝这种验证；大数据改用可以证明答案的构造。输入非法或参考计算不能完成时，报告 JUDGE_ERROR，不把它归咎于候选算法。

我还会故意提交错误代码，确认判题器确实能报错。一个对任何程序都显示 AC 的工具，界面再像在线判题站，也没有验证价值。

这里的超时约束针对整批程序运行，耗时包含进程启动和输入输出，不是纯 solve 耗时。工具只供本机可信代码使用，没有公共在线判题站的操作系统隔离和内存限额计量。

8. 这道题留给我的两点认识

固定一个变量，并不自动意味着剩下的变量独立。这一题能拆，是因为固定 b 后，目标函数里没有把 a 与 c 联系起来的项，且两者的可选范围互不约束。

从二分到线性，也不是“看到有序就套双指针”：还要观察查询值 b 的顺序，以及最近点的位置能不能回退。每次独立查询只利用了一半的有序性；把查询之间的关系利用起来，才消除了重复查找。

下一篇把距离补回 |c-a|。第一步我仍然想固定 b，但这一次，分别找最近值会被一个只有四个输入元素的反例推翻。