携程 9 月 20 日机考笔试题解：三联抽检组与卡槽最少移动

《面试题目》

1. 三联抽检组：一条质检线上依次排出 n 件工件，第 i 件工件的质量读数为 a[i]（下标从 1 开始），另有非负整数公差 t。对每个满足 1 ≤ i ≤ n−2 的下标 i，把连续三件 a[i]、a[i+1]、a[i+2] 看成一个候选抽检组；若三件读数的最大值与最小值之差 ≤ t，则该抽检组合格。可以选用任意多个合格抽检组，也可以一个都不选，被选用的抽检组两两不能占用同一件工件。求最多能选出多少个合格抽检组。输入第一行两个整数 n 和 t，第二行 n 个整数表示质量读数；样例输入 10 5 与 10 12 8 15 11 14 20 22 19 3，输出 3。
2. 测试台卡槽的最少移动：一条测试台上有 n 个卡槽排成一行，编号从 1 到 n。调试员一开始站在第 1 号卡槽，要把探针移到第 k 号卡槽。每次可以把探针从当前卡槽跳到任意另一个卡槽，但不能跳到 [1, n] 之外，一次移动的步长是两卡槽编号差的绝对值。监测系统会记下步长落在闭区间 [x, y] 内的移动，调试员只做不会被记录的移动。可以证明当 x ≥ 2 时他一定能到达第 k 号卡槽，求最少需要多少次移动。输入第一行一个整数 T，表示询问组数。（原帖在输入描述处截断，第二题的完整题面与数据范围缺失。）

《参考解析》

1. 三联抽检组：从左到右贪心。每个合格组固定占用连续 3 个位置，所以任意两个被选中的组，其起点下标至少相差 3。从左到右扫描下标 i：如果以 i 开头的三件合格，就立刻取走这一组并把 i 直接加 3；否则 i 加 1。这里不需要回头：放弃当前最靠左的合格组，后面的组最多也只能占用这三件中的一部分，能选出的组数不会变多，而每取走一组都会把后面可选的位置整体右推，不会让局面变差。判断合格只要算三件的最大值减最小值是否 ≤ t，全程一遍扫描，时间复杂度 O(n)、空间复杂度 O(1)。这段 C++ 写法如下：

int ans = 0;
for (int i = 0; i + 2 < n; ) {
    int mx = max(a[i], max(a[i + 1], a[i + 2]));
    int mn = min(a[i], min(a[i + 1], a[i + 2]));
    if (mx - mn <= t) { ++ans; i += 3; }
    else ++i;
}

2. 卡槽最少移动：把步长限制翻译成两种可用步。允许的移动只有两类——小步 s ∈ [1, x−1]，或者大步 s ∈ [y+1, n−1]；闭区间 [x, y] 里的步长一律不能被监测系统记录，等于不可用。设一共走了 A 步大小为 p 的正向大步、B 步大小为 q 的反向大步、以及若干小步，最终净位移必须是 k−1。因为往返本身会抵消位移，最少步数一定出现在「枚举用了几次大步」这一层：大步负责快速拉开或越过距离，小步（至多 x−1）负责把落点精确对准 k。得到净位移 k−1 所需的最小总步数，就是所有可行的大步次数里总步数的最小值。x = 1 时小步只能是 0，位移只能靠大步凑，所以原题才强调 x ≥ 2 时一定可达。

3. 笔试里值得注意的两个坑。一是样例只给一组，别拿它当边界：n 很小时（比如 n < 3）第一题答案必然是 0，直接返回。二是第二题的读入是 T 组询问，属于多测数据，每组都要重新初始化，别把上一组的状态带进下一组——这类题在机考里最常见的失分点不是算法，而是多测没清空。