Минимум суммы абсолютных значений

Question

Постановка задачи:

Есть 3 массива A, B, C, все из которых заполнены натуральными числами, и все три массива имеют одинаковый размер.

Найдите min (| a-b | + | b-c | + | c-a |), где a находится в A, b находится в B, c находится в C.

---

Я работал над проблемой все выходные. Друг сказал мне, что это можно сделать за линейное время. Я не понимаю, как это могло быть возможно.

Как бы вы это сделали?

Answer 1

Ну, я думаю, что могу сделать это за 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 мимо K до того, как i достигнетI.Как все выглядит перед тем, как мы выполняем это приращение?Ну, C[k] является наименьшим из трех на данный момент, потому что мы собираемся увеличить k.A[i] меньше или равно A[I], потому что i < I и A отсортированы.Наконец, j <= J потому что k <= K (по нашей лемме), поэтому B[j] также меньше A[I].В совокупности это означает, что наша сумма abs-diff на данный момент на меньше , чем 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 равны.Но я думаю, что детали могут быть проработаны довольно легко.

Answer 2

Я бы написал действительно простую программу, подобную этой:

#!/usr/bin/python
import sys, os, random
A = random.sample(range(100), 10)
B = random.sample(range(100), 10)
C = random.sample(range(100), 10)
minsum = sys.maxint
for a in A:
 for b in B:
  for c in C:
   print 'checking with a=%d b=%d c=%d' % (a, b, c)
   abcsum = abs(a - b) + abs(b - c) + abs(c - a)
   if abcsum < minsum:
    print 'found new low sum %d with a=%d b=%d c=%d' % (abcsum, a, b, c)
    minsum = abcsum

И проверяйте это снова и снова, пока я не увижу какой-то паттерн. Шаблон, который я нашел здесь, - это то, что и следовало ожидать: числа, которые находятся ближе всего друг к другу в каждом наборе, независимо от того, являются ли числа «высокими» или «низкими», являются теми, которые дают наименьшую минимальную сумму. Так что это становится проблемой ближайшего числа. Что бы это ни стоило, вероятно, не так много.