HZOJ-838：2020年数据结构41题

题目描述

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

程序中的主要部分已经帮你写好了，你只需要将如下代码拷贝到你的环境中，并且补充 func函数功能即可。函数功能描述如下：

输入参数

输入三个参数，分别为存储三个非空集合的队列

返回值说明

返回一个整形值，表示所有可能的三元组（a, b, c）（a∈S1,b∈S2,c∈S3）中的最小距离

#include <stdio.h>
#include <math.h>
int n, m, k;

int min(int i, int j, int k) {
	i = i < j ? i : j;
	i = i < k ? i : k;
	return i;
}

int func(int *arr1, int *arr2, int *arr3) {
	int i = 0, j = 0, c = 0, ans = 0x3f3f3f3f;
	while (i < n && j < m && c < k) {
		int t = abs(arr1[i] - arr2[j]) + abs(arr2[j] - arr3[c]) + abs(arr1[i] - arr3[c]);
		if (t < ans) ans = t;
		int temp = min(arr1[i], arr2[j], arr3[c]);
		if (temp == arr1[i]) i++;
		else if (temp == arr2[j]) j++;
		else c++;
	}
	return ans;
}

int main() {
	scanf_s("%d %d %d", &n, &m, &k);
	int* arr1 = (int*)malloc(sizeof(int) * n);
	int* arr2 = (int*)malloc(sizeof(int) * m);
	int* arr3 = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < n; i++) scanf_s("%d", &arr1[i]);
	for (int i = 0; i < m; i++) scanf_s("%d", &arr2[i]);
	for (int i = 0; i < k; i++) scanf_s("%d", &arr3[i]);
	
	printf("%d", func(arr1, arr2, arr3));

	return 0;
}

文章来源地址https://uudwc.com/A/AAkpq