三个有序数组找最小距离从固定 b 到线性扫描我最开始做到这道题时题面里的距离只有两项。后来才发现它并不是原始 408 题目的正确距离定义。但这个错误版本本身仍是一个完整的问题而且从它走到正确版本能看清楚目标函数只多一项算法为什么会改变。这一篇先把两项距离的问题讲明白三个数组非空、按非递减顺序排列允许重复元素。目标是找出最小距离及任意一组达到它的元素。1. 我的切入点先把 b 定下来我看到式子之后第一反应是a只和b有关c也只和b有关a和c之间没有直接的一项。所以先固定b。此时挑a不会限制挑c两个选择可以独立完成这个等号可以从两方面理解任意组合都不可能小于右边两个最小值之和分别选到两个最小值又确实能组成一组合法答案。比如A[1,4,8]、B[5,10]、C[2,6,12]固定的bA中最近元素C中最近元素距离54611210812224枚举B的所有元素就不会漏掉最优组合中的b。此时根本不用同时枚举a、b、c。2. 第一个正确解再利用有序性记三个数组的长度分别为 n|A|、m|B|、k|C|。如果每次固定 b都扫描 A 和 C复杂度是 O(m(nk))。数组有序后可以二分找第一个大于等于b的位置p。最近值只可能出现在p和p-1左边越往左越远右边越往右越远。p在数组两端时仅检查存在的候选。方案每个b做什么总时间扫描找最近值扫描A、CO(m(nk))二分找最近值找插入位置及其左邻居O(m(log(n1)log(k1)))单调指针沿用上次的位置并向右推进O(nmk)复杂度中写log(n1)是为了连长度为1的情况也能明确包含常数开销。3. B也有序上一次的位置还能用如果b按照从小到大的顺序出现A中最靠右的最近点位置不会往左走。C同理。对两个不同的值xyy不比x远当且仅当随着b增大一旦y已经不比x远这个关系就不会反转。如果xy两个距离始终相等可以直接选择右边的位置。因此维护A的指针i、C的指针j每次固定新的b只需继续向右寻找最近点。对固定b有序数组的距离先不增、后不减。跳过相等距离再在下一项严格变远时停下就找到最靠右的最小值。不会出现“先严格变远后面又更近”的情况。4. 原来写的严格小于为什么需要修正最初的伪代码用的是只有下一项距离严格更小才让指针右移。但数组可能有重复元素A [1, 1, 4] B [4] C [4]从A[0]开始下一项还是1距离没有严格减小指针就停住了。算出的距离是3实际最小值是0。位置iA[i]到b4的距离严格小于版本小于等于版本013下一项等距停住等距继续113未访问下一项更近继续240未访问到达末尾得到正确最近点所以判断应当使用。它既跨过重复元素也统一采用最靠右的最近点方便复用到下一个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 位整数距离最大可达 8589934590A 和 C 都选 2147483647B 选 -2147483648。因此元素使用int32_t距离使用int64_t。为什么程序分成这几个部分算法不是一份必须靠输入输出才能调用的脚本。solve只接收数组和长度返回Answer不读输入、不打印结果因此可以单独观察它的指针状态也能在测试时直接替换另一种算法。部分负责什么为什么单独放在这里distance_between先扩大整数类型再计算绝对值两个最近点扫描共用同一种安全距离计算solve/Answer求最优距离并记录所选元素把算法与输入格式分开避免只得到距离却丢失组合read_array/main读入、检查有序、分配释放、输出多组测试可以共用同一个求解函数Answer除了距离还保存三元组。这既回应了“找一组元素”的题目要求也让验证器能检查输出的答案是否真的由合法元素产生。注意solve的 O(1) 额外空间不包括调用者已经存下来的输入数组。程序结构分开之后这两个空间开销也更容易讲清楚。6. 为什么结果一定最优为什么总时间是线性每次处理b时两根指针分别指向A、C中最靠右的最近点。第一次从数组开头寻找后续因为最近位置不回退可以从上次位置继续寻找。距离的先不增后不减性质保证扫描停止的位置就是最近点。固定b的两个独立最小值之和就是该b能得到的最小距离。把B中的所有b处理完并取最小值就得到全局最优答案。尽管for里还有while两个指针都不回退i最多前进n-1次j最多前进k-1次B遍历m次。每次成功推进与每轮末尾的一次失败判断加起来仍是O(nmk)。求解函数只使用指针和一组答案额外空间O(1)。完整C程序存放输入数组的空间为O(nmk)两者需要区分。7. 没有现成判题站怎样检查自己的算法我给这道题配了本地判题器。小规模参考解直接枚举所有三元组使用BigInt算距离与单调指针完全独立。判题也不只看一个预先写好的三元组而是检查输出的a、b、c分别属于对应数组。报告的D与这三个值实际算出的距离一致。D等于暴力参考解求出的最小值。除了样例还包含重复元素反例、负数、等距、整数极值以及小值域完整穷举和固定种子的随机数据。这里的“小值域完整穷举”有明确范围元素取自 {-1,0,1}长度为 13列出所有非递减数组。三种长度分别有 3、6、10 个数组共 19 个A、B、C 任意组合一共 19³6859 组。它不是对任意整数、任意长度的穷举但能系统覆盖短数组中的重复值、等距和大小关系。还有几种可以交叉检查的性质交换A和C不改变最优距离往数组里加入已有值的副本不改变答案三个数组同时加一个常数不改变答案合法范围内同时乘正整数距离应同比例增大。大数据使用三数组共有元素的案例能直接证明最小值为0。这里不会为了验证线性解在200000元素规模上运行立方复杂度暴力。测试是为了找反例和检查实现正确性仍由上面的拆分与单调性证明支撑。这道题值得保留的推导顺序是先固定b得到正确解再利用数组有序做二分最后发现查询也有序让已有搜索结果服务于下一次查询。这次实际运行的结果如下。两个批次有重复用例不把它们相加当成不同用例数。检查实际结果默认种子 408随机 2000 组加穷举与构造数据9785 组全部通过种子 12345随机 10000 组加穷举与构造数据21479 组全部通过故意将改成重复元素用例被判错应为 0实际为 3错误三元组、编译失败、运行失败、超时判题器分别识别不把运行成功当成答案正确如果只想先复现最关键的检查将前面的程序保存为solution.c使用支持 C11 的 GCC 编译gcc -stdc11 -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 运行。它只展示小数据参考解与答案检查不包含完整的编译器调用、测试生成器和网页界面。不要在大数组上运行三重枚举。完整工具把一次提交分成几个步骤执行 GCC 编译候选 C 程序失败时报告 CE不继续处理测试数据。题目模块生成或解析输入检查数组是否有序、长度和元素是否在约定范围内再计算参考距离。如果代码和输入同时有错这个顺序会先报告 CE。将多组输入送入程序收集输出。非正常退出报告 RE执行超时报告 TLE。按行检查四个整数、元素归属、距离一致性和最优性失败报告 WA而不是要求它与参考解选中同一个三元组。保存第一组失败输入、参考距离和实际输出单独重跑反例。只有整批都通过才报告 AC。参考解也有边界完整工具只允许小数据进行暴力枚举超过 2000000 个三元组时拒绝这种验证大数据改用可以证明答案的构造。输入非法或参考计算不能完成时报告 JUDGE_ERROR不把它归咎于候选算法。我还会故意提交错误代码确认判题器确实能报错。一个对任何程序都显示 AC 的工具界面再像在线判题站也没有验证价值。这里的超时约束针对整批程序运行耗时包含进程启动和输入输出不是纯solve耗时。工具只供本机可信代码使用没有公共在线判题站的操作系统隔离和内存限额计量。8. 这道题留给我的两点认识固定一个变量并不自动意味着剩下的变量独立。这一题能拆是因为固定 b 后目标函数里没有把 a 与 c 联系起来的项且两者的可选范围互不约束。从二分到线性也不是“看到有序就套双指针”还要观察查询值 b 的顺序以及最近点的位置能不能回退。每次独立查询只利用了一半的有序性把查询之间的关系利用起来才消除了重复查找。下一篇把距离补回|c-a|。第一步我仍然想固定 b但这一次分别找最近值会被一个只有四个输入元素的反例推翻。