绝对值之和的最小值 [英] Minimum of sum of absolute values

问题描述

问题陈述:

有 3 个数组 A,B,C 都用正整数填充，并且三个数组的大小都相同.

There are 3 arrays A,B,C all filled with positive integers, and all the three arrays are of the same size.

求 min(|a-b|+|b-c|+|c-a|)，其中 a 在 A 中，b 在 B 中，c 在 C 中.

Find min(|a-b|+|b-c|+|c-a|) where a is in A, b is in B, c is in C.

我整个周末都在解决这个问题.一位朋友告诉我，它可以在线性时间内完成.我不明白这怎么可能.

I worked on the problem the whole weekend. A friend told me that it can be done in linear time. I don't see how that could be possible.

你会怎么做?

推荐答案

好吧，我想我可以在 O(n log n) 内完成.如果数组最初是排序的，我只能做 O(n).

Well, I think I can do it in O(n log n). I can only do O(n) if the arrays are initially sorted.

首先，请注意您可以在不更改表达式值的情况下随意置换 a、b、c.所以让 x 是 a,b,c 中最小的一个；让 y 成为三者的中间；并设 z 为最大值.然后请注意，表达式正好等于 2*(z-x).(这很容易看到......一旦你按顺序排列了三个数字，x < y <z，总和就是 (yx) + (zy) +(zx) 等于 2*(zx))

First, observe that you can permute a,b,c however you like without changing the value of the expression. So let x be the smallest of a,b,c; let y be the middle of the three; and let z be the maximum. Then note that the expression just equals 2*(z-x). ( This is easy to see... Once you have the three numbers in order, x < y < z, the sum is just (y-x) + (z-y) + (z-x) which equals 2*(z-x))

因此，我们真正想做的就是找到三个数字，使外面的两个尽可能靠近，而另一个数字夹在"它们之间.

Thus, all we are really trying to do is find three numbers such that the outer two are as close together as possible, with the other number "sandwiched" between them.

所以首先以 O(n log n) 对所有三个数组进行排序.维护每个数组的索引；调用这些 i、j 和 k.将所有三个初始化为零.无论哪个索引指向最小值，递增该索引.即如果A[i]小于B[j]和C[k]，则递增i;如果 B[j] 最小，则递增 j；如果 C[k] 最小，则增加 k.重复，跟踪 |A[i]-B[j]|+ |B[j]-C[k]|+ |C[k]-A[i]| 整个时间.你在这次游行中观察到的最小值就是你的答案.(当三个中最小的在其数组的末尾时，停止，因为你已经完成了.)

So start by sorting all three arrays in O(n log n). Maintain an index into each array; call these i, j, and k. Initialize all three to zero. Whichever index points to the smallest value, increment that index. That is, if A[i] is smaller than B[j] and C[k], increment i; if B[j] is smallest, increment j; if C[k] is smallest, increment k. Repeat, keeping track of |A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]| the whole time. The smallest value you observe during this march is your answer. (When the smallest of the three is at the end of its array, stop because you are done.)

在每一步中，您都将一个索引添加到一个索引；但是您只能在结束之前为每个数组执行 n 次.所以这最多3*n步，也就是O(n)，小于O(n log n)，也就是说总时间是O(n log n).(或者如果您可以假设数组已排序，则只需 O(n).)

At each step, you add one to exactly one index; but you can only do this n times for each array before hitting the end. So this is at most 3*n steps, which is O(n), which is less than O(n log n), meaning the total time is O(n log n). (Or just O(n) if you can assume the arrays are sorted.)

证明这可行的草图:假设 A[I]、B[J]、C[K] 是 <构成实际答案的代码>a、b、c；即，它们具有最小的 |a-b|+|b-c|+|c-a|.进一步假设 a > b > c;其他情况的证明是对称的.

Sketch of a proof that this works: Suppose A[I], B[J], C[K] are the a, b, c that form the actual answer; i.e., they have the minimum |a-b|+|b-c|+|c-a|. Suppose further that a > b > c; the proof for the other cases is symmetric.

引理:在我们的行进过程中，我们不会将 j 增加超过 J 直到我们将 k 增加超过 K.证明:我们总是递增最小元素的索引，当k <= K时，B[J] >C[k].所以当j=J和k <= K时，B[j]不是最小元素，所以我们不递增j.

Lemma: During our march, we do not increment j past J until after we increment k past K. Proof: We always increment the index of the smallest element, and when k <= K, B[J] > C[k]. So when j=J and k <= K, B[j] is not the smallest element, so we do not increment j.

现在假设我们在 i 到达 I 之前增加 k 超过 K.在我们执行那个增量之前，事情是什么样子的?嗯，C[k] 是当时三个中最小的一个，因为我们即将增加 k.A[i] 小于或等于 A[I]，因为 i <I 和 A 已排序.最后，j <= J 因为 k <= K (由我们的引理)，所以 B[j] 也小于 <代码>A[I].综合来看，这意味着我们此时的 sum-of-abs-diff less 小于 2*(c-a)，这是一个矛盾.

Now suppose we increment k past K before i reaches I. What do things look like just before we perform that increment? Well, C[k] is the smallest of the three at that moment, because we are about to increment k. A[i] is less than or equal to A[I], because i < I and A is sorted. Finally, j <= J because k <= K (by our Lemma), so B[j] is also less than A[I]. Taken together, this means our sum-of-abs-diff at this moment is less than 2*(c-a), which is a contradiction.

因此，在 i 到达 I 之前，我们不会将 k 递增到 K.因此，在我们进行 i=I 和 k=K 期间的某个时间点.根据我们的引理，此时 j 小于或等于 J.所以此时，B[j] 小于其他两个，j 将递增；或 B[j] 介于其他两者之间，我们的和只是 2*(A[i]-C[k])，这是正确的答案.

Thus, we do not increment k past K until i reaches I. Therefore, at some point during our march i=I and k=K. By our Lemma, at this point j is less than or equal to J. So at this point, either B[j] is less than the other two and j will get incremented; or B[j] is between the other two and our sum is just 2*(A[i]-C[k]), which is the right answer.

这个证明是草率的；特别是，它未能明确说明 a、b、c 中的一个或多个相等的情况.但我认为这个细节很容易解决.

This proof is sloppy; in particular, it fails to explicitly account for the case where one or more of a,b,c are equal. But I think that detail can be worked out pretty easily.

这篇关于绝对值之和的最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！