考研笔记

板子：三元组最小距离（三指针）

在数轴上看，最大值最小值。三个指针同时往前走，每次让当前最小的那个前进一步。

代码

int absv(int x) { return x < 0 ? -x : x; }
 
int minDist(int A[], int n, int B[], int m, int C[], int p) {   // 三个升序数组
    int i = 0, j = 0, k = 0, ans = 0x7fffffff;         // ans 初值取 int 的最大值
    while (i < n && j < m && k < p) {                  // 任何一个数组走完就停
        int d = absv(A[i] - B[j]) + absv(B[j] - C[k]) + absv(C[k] - A[i]);   // 当前三元组的距离
        if (d < ans) ans = d;
        if (A[i] <= B[j] && A[i] <= C[k]) i++;         // 谁最小，谁往后走
        else if (B[j] <= A[i] && B[j] <= C[k]) j++;
        else k++;
    }
    return ans;
}

复杂度：时间 ，空间 。

例（2020 原题）：，，，最小距离是 ，对应三元组 。

为什么移动最小的那个

设当前最小的是 A[i]。它和 B、C 后面的任何元素组成三元组，最大值只会更大或不变，距离不会比现在更小。所以 A[i] 已经没用了，可以跳过。

易错点

  • 任何一个数组走完就停：最小值那一组已经没有更大的元素了，再往后不可能更优。
  • ans 的初值要足够大，0x7fffffff 就是 INT_MAX，写成这样可以不引头文件。
  • 暴力三重循环 也是正确解，考场没思路先写它保底。

链接

反向链接