UVa 11057

http://uva.onlinejudge.org/external/110/11057.html

Una posible solución seria iterar para cada libro disponible, si el libro tiene precio p, podemos calcular el valor M-p y buscar si tenemos otro libro con este precio, de esta manera encontramos un par de libros que son una solución.  Este método es O(n^2) y dado que podemos tener hasta 10000 libros, esta solución es demasiado lenta. Sin embargo, si ordenamos inicialmente los precios de los libros, podemos aplicar una búsqueda binaria para determinar si existe el valor M-p, y de esta forma obtenemos un algoritmo O(n log n). Solo hay que tener en cuenta no escoger el mismo libro 2 veces, ya que esto no es una solución valida.

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s