ZYF011 三元组的最小距离
大约 2 分钟双指针
ZYF011 三元组的最小距离
【算法标签】 双指针、滑动窗口
【语法标签】 :数组、for循环、while循环、long long、min、max
给定三个非空、升序的整数数组 ,长度分别为 ,元素在$ [−109,109]$之间。
距离定义为三元组 的
D=∣a−b∣+∣b−c∣+∣c−a∣其中 。
求所有可能的三元组中 的最小值。
注意:
推导:设 ,则中间值记为 ,有:
∣a−b∣+∣b−c∣+∣c−a∣=(M−mid)+(mid−m)+(M−m)=2(M−m)所以题目可以转化为:找到三个数 ,使得 最小,然后乘以 就是答案。
其实,就是说, 是三个数中最大的那个, 是三个数中最小的那个, 是三个数中中间那个。
解题思路
我们要最小化 ,等价于让三个数尽量接近。
由于三个数组是分别有序的,可以利用类似“三指针归并”的思想,每次移动最小的那个元素,逐步逼近。
算法步骤( 时间, 空间):
- 初始化指针 ,分别指向三个数组开头。
- 设 ,计算 ,更新答案的最小值。
- 比较 三个值,找到最小的那个值所在的数组,将该数组的指针向后移动一位(因为移动最小的数有可能让最小值变大,从而让最大值和最小值的差距变小)。
- 重复步骤 ,直到某一个数组指针走到末尾为止。
- 输出过程中出现的最小 值。
为什么可行:
因为固定其他两个数,最小值增加可能让区间长度减小。我们要让三元组的最大值和最小值尽量接近,移动最小的元素是尝试缩小差距的必然选择。
这种方法本质是枚举所有可能的最小值位置,每次更新答案。因为每个指针只会往后移动,总步数 。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N];
int main(){
int l, m, n;
cin >> l >> m >> n;
for (int i = 0; i < l; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
long long ans = 1e18;
int i = 0, j = 0, k = 0;
while (i < l && j < m && k < n){
int x = a[i];
int y = b[j];
int z = c[k];
long long t = max(max(x, y), z) - min(min(x, y), z);
ans = min(ans, t);
// 最小的那个数对应的指针向右移动
if (x <= y && x <= z){
i++;
} else if (y <= x && y <= z){
j++;
} else {
k++;
}
}
cout << ans * 2;
return 0;
}