[C算法]005-寻找最小的三元组距离

均采用C语言来编写，版本为C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

题目

2020年真题

定义三元组 $(a,b,c) (a,b,c \text{ 均为整数})$ 的距离 $D=|a-b|+|a-c|+|b-c|$。
给定三个非空整数集合 $S_1$，$S_2$ 和 $S_3$，按升序分别存储在3个数组中.
请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)(a∈S1,b∈S2,c∈S3)$ 中最小距离。
例如：$S_1=\{-1,0,9\}，S_2=\{-25,-10,10,11\}，S_3=\{2,9,17,30,41\}$，则最小距离为2，相应的三元组为 $(9,10,9)$。

分析

这道算法既考察数学洞察力，也考察对双指针（在这里是三指针）技巧的运用。让我们一步步来拆解它。

首先，我们看这个距离公式：$D=|a-b|+|a-c|+|b-c|$。乍一看它包含三个绝对值，计算起来似乎有点繁琐。

为了简化问题，假设 $a \le b \le c$

在这种假设下，我们计算得 $|a-b|+|a-c|+|b-c|=2c-2a$

也就是 $D=2\times(\text{最大}-\text{最小})$

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 1. 基础工具：static inline (静态内联)
// 编译器会把它们像宏一样展开，但完全安全
static inline int max_val(int a, int b) { return a > b ? a : b; }
static inline int min_val(int a, int b) { return a < b ? a : b; }

// 2. 三数最值工具
static inline int max3(int a, int b, int c) {
    return max_val(a, max_val(b, c));
}

static inline int min3(int a, int b, int c) {
    return min_val(a, min_val(b, c));
}

// 3. 核心逻辑
void find_min_of_trip(int a[], int n_a, int b[], int n_b, int c[], int n_c) {
    int i = 0, j = 0, k = 0;
    int min_dist = INT_MAX; // 初始化为最大整数
    
    // 用于记录最终结果
    int res_a = a[0], res_b = b[0], res_c = c[0];

    while (i < n_a && j < n_b && k < n_c) {
        // 取值
        int val_a = a[i];
        int val_b = b[j];
        int val_c = c[k];

        // 计算：利用数学等价公式 2 * (max - min)
        // 编译器会极度优化这部分代码
        int current_min = min3(val_a, val_b, val_c);
        int current_max = max3(val_a, val_b, val_c);
        int current_dist = 2 * (current_max - current_min);

        // 更新最优解
        if (current_dist < min_dist) {
            min_dist = current_dist;
            res_a = val_a;
            res_b = val_b;
            res_c = val_c;
            
            // 小优化：如果距离已经是0了，不可能更小了，直接收工
            if (min_dist == 0) break; 
        }

        // 移动指针：谁是最小的，谁就往后移
        // 这里直接用我们算好的 current_min，逻辑清晰且安全
        if (val_a == current_min) i++;
        else if (val_b == current_min) j++;
        else k++;
    }

    printf("最小距离为%d，三元组为(%d, %d, %d)\n", min_dist, res_a, res_b, res_c);
}

int main() {
    int s1[] = {-1, 0, 9};
    int s2[] = {-25, -10, 10, 11};
    int s3[] = {2, 9, 17, 30, 41};
    find_min_of_trip(s1, 3, s2, 4, s3, 5);
    return 0;
}