绝对值之和的最小值
问题陈述：
有3个数组A，B，C都用正整数填充，并且所有三个数组的大小相同。
找出min（| ab | + | bc | + | ca |），其中a在A中，b在B中，c在C中。
我整个周末都在研究这个问题。一位朋友告诉我，可以在线性时间内完成。我不知道怎么可能。
你会怎么做？
回答：
好吧，我想我可以在O（n log n）中做到这一点。如果数组最初是排序的，我只能执行O（n）。
首先，注意观察，你可以置换a，b，c但是你喜欢不改变表达式的值。因此，让我们x是最小的a，b，c，让y它们成为三个的中间
并z设为最大。然后注意，表达式等于2*(z-x)。（编辑：这很容易看到。。。按顺序排列三个数字后x < y < z，总和(y-x) +
(z-y) + (z-x)等于2*(z-x)）
因此，我们真正想做的就是找到三个数字，以使外部两个数字尽可能靠近，而另一个数字“夹在中间”。
因此，首先对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]|整个时间。您在这次游行中观察到的最小值就是您的答案。（当三个中最小的一个位于其数组的末尾时，请停止，因为您已完成。）
在每一步中，您都将一个索引添加到一个索引中。但您只能n在每次结束前对每个数组执行此操作。因此，这最多是3*n步骤，即O（n），小于O（n log
n），这意味着总时间为O（n log n）。（或者如果可以假设数组已排序，则只是O（n）。）
证明这个作品的素描：假设A[I]，B[J]，C[K]是a，b，c形成实际的答案;
即，它们具有最小值|a-b|+|b-c|+|c-a|。进一步假设a> b> c; 其他情况的证明是对称的。
引理：在我们行军，我们没有增量j过去J，直到我们增加后k过去K。证明：我们总是增加最小元素的索引，当k <= K，时B[J] >
C[k]。因此，当j=J和k <= K，B[j]是不是最小的元素，所以我们没有增加j。
现在假设我们在到达之前增加k过去。在执行该增量之前，情况如何？好吧，那是那时三者中最小的，因为我们将要增加。
小于或等于，因为和已排序。最后，因为（由我们的引理），所以也小于。总之，这意味着我们在这一刻总和法ABS-DIFF是 少
比，这是一个矛盾。K``i``I``C[k]``k``A[i]``A[I]``i < I``A``j <= J``k <= K``B[j]``A[I]
__2*(c-a)
因此，我们直到达到才增加k过去。因此，在我们的行军过程中的一些点和。根据我们的引理，此时小于或等于。因此，在这一点上，任一个小于其他两个，并且将递增；或在其他两个之间，我们的总和就是，这是正确的答案。K``i``I``i=I``k=K``j``J``B[j]``j``B[j]``2*(A[i]-C[k])
这个证明很草率；特别是，它没有明确地考虑其中一个或多个的情况下a，b，c是相等的。但是我认为可以很容易地得出细节。
以上是 绝对值之和的最小值 的全部内容， 来源链接： utcz.com/qa/420487.html
