Para esta tarea, su código debe tomar dos matrices ordenadas de enteros X e Y como entrada. Debe calcular la suma de las distancias absolutas entre cada número entero en X y su número más cercano en Y.

Ejemplos:

X = (1 5,9)
Y = (3,4,7)

La distancia es 2 + 1 + 2.

X = (1,2,3)
Y = (0,8)

La distancia es 1 + 2 + 3.

Su código puede recibir información de cualquier manera que sea conveniente.

La restricción principal es que su código debe ejecutarse en tiempo lineal en la suma de la longitud de las dos matrices. . (Puede suponer que agregar dos enteros lleva tiempo constante).

Haskell , 70 64 bytes

a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_<-d,a%c>a%e=x#d|1>0=a%c+b#y
_#_=0

Pruébalo en línea!

Explicación

Primero definimos (%)como la diferencia absoluta entre dos números. Luego definimos (#)ser la función interesante. En la primera línea, coincidimos cuando ambas listas no están vacías:

x@(a:b)#(c:d:e)

En nuestro primer caso de aquí nos atamos da e:_con e:_<-d. Esto asegura que dno esté vacío y establece su primer elemento e.

Entonces, si el segundo elemento de ( ) está más cerca que la primera ( ) al primer elemento de X ( ), volvemos retirar el primer elemento de Y y llamar de nuevo con la misma X .$Y$ec$X$ax#d$Y$$X$

Si hacemos coincidir el patrón pero no pasamos la condición que hacemos:

a%c+b#y

Lo cual elimina el primer elemento de y agrega la diferencia absoluta del primer elemento de X al resultado restante.$X$$X$

Finalmente, si no coincidimos con el patrón, devolvemos . No coincidir con el patrón significa que X debe estar vacío porque Y no puede estar vacío.$0$$X$$Y$

Este algoritmo tiene notación de orden .$O(|X|+|Y|)$

Haskell , 34 bytes

Así es como lo haría en tiempo :$O(\left|X\right|\times\left|Y\right|)$

x#y=sum[minimum$abs.(z-)<$>y|z<-x]

Pruébalo en línea!

Python 2 , 124 120 bytes

X,Y=input()
i=j=s=0
while i<len(X):
 v=abs(Y[j]-X[i])
 if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1
 else:s+=v;i+=1
print s

Pruébalo en línea!

Se guardaron 4 bytes moviéndose al programa versus la función.

Es posible cumplir con la restricción de complejidad de tiempo porque ambas listas están ordenadas. Tenga en cuenta que cada vez alrededor del ciclo, ise incrementa o jse incrementa. Por lo tanto, el bucle se ejecuta en la mayoría de los len(X)+len(Y)casos.

C (gcc), 82 bytes

n;f(x,y,a,b)int*x,*y;{for(n=0;a;)--b&&*x*2-*y>y[1]?++y:(++b,--a,n+=abs(*x++-*y));}

Esto toma la entrada como dos matrices enteras y sus longitudes (ya que C no tiene forma de obtener su longitud de otra manera). Se puede mostrar que se ejecuta O(a+b)porque ao bse disminuye en cada iteración del bucle, que termina cuando allega 0(y bno se puede disminuir a continuación 0).

Pruébalo en línea!

n;                     // define sum as an integer
f(x,y,a,b)             // function taking two arrays and two lengths
int*x,*y;              // use k&r style definitions to shorten function declaration
{
 for(n=0;              // initialize sum to 0
 a;)                   // keep looping until x (the first array) runs out
                       // we'll decrement a/b every time we increment x/y respectively
 --b&&                 // if y has ≥1 elements left (b>1, but decrements in-place)...
 *x*2-*y>y[1]?         // ... and x - y > [next y] - x, but rearranged for brevity...
 ++y:                  // increment y (we already decremented b earlier);
 (++b,                 // otherwise, undo the in-place decrement of b from before...
 --a,n+=abs(*x++-*y))  // decrement a instead, add |x-y| to n, and then increment x
;}

Algunas notas:

• En lugar de indexar en las matrices, el incremento de los punteros y la eliminación de referencias directamente ahorra suficientes bytes para que valga la pena ( *xvs x[a]y y[1]vs y[b+1]).

• La --b&&condición se verifica de b>1forma indirecta; si bes así 1, se evaluará a cero. Como esto se modifica b, no necesitamos cambiarlo en la primera rama del ternario (que avanza y), pero sí necesitamos volver a cambiarlo en la segunda (que avanza x).

• No returnse necesita ninguna declaración, porque la magia negra. (Creo que se debe a que la última declaración que se evaluará siempre será la n+=...expresión, que usa el mismo registro que el utilizado para los valores de retorno).

Ruby, 88 bytes

->(p,q){a=q.each_cons(2).map{|a|a.sum/a.size}
x=a[0]
p.sum{|n|x=a.pop if n>x
(n-x).abs}}

Pruébalo en línea!

Además, por diversión, una función anónima más corta que no cumple con las restricciones de complejidad:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}

JavaScript (Node.js) , 80 bytes

x=>g=(y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?g(y,i+!t,j+t)+!t*(d>0?d:-d):0

• Se ejecuta en O (| X | + | Y |): cada recursión se ejecuta en O (1), y es recursiva | X | + | Y | veces.
  • x, yse pasan por referencia, que no copian el contenido
• 1/ves falso si x[i]está fuera de rango, de lo contrario es cierto
• t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]es falso siempre que se cumplan las siguientes condiciones. Y lo que significa y[j]es el número más cercano a veny
  • ves menor (y[j]+y[j+1])/2o
  • y[j+1]está fuera de rango, lo que convertiría NaNy compararía con el NaNrendimientofalse
    • es por eso que no podemos voltear el >signo para guardar 1 byte más
• tsiempre es un valor booleano y *conviértalo a 0/ 1antes de calcular

Pruébalo en línea!

Mathematica, 40 bytes

x = {1, 5, 9};
y = {3, 4, 7};

Norm[Flatten[Nearest[y] /@ x] - x]

Si debe crear un programa completo, con entradas:

f[x_,y_]:= Norm[Flatten[Nearest[y] /@ x] - x]

Aquí está el tiempo para hasta 1,000,000 de puntos (muestreados cada 10,000) para y:

Cercano a lineal.