11057 Exact Sum
http://acm.uva.es/p/v110/11057.htmlEn este problema, nos dan el precio de varios libros, de los cuales debemos comprar 2 y que su precio sea exactamente el dinero que tenemos. Nos garantizan que habra solucion, asi que no hay que pensar en ese caso.
La clave para resolverlo es hacerse un array con los distintos precios de los libros y ordenarlo crecientemente (menos a mayor). Podemos ordenarlo por ejemplo mediante la orden qsort de C.
Tras tenerlos ordenados, ponemos una variable que apunte a la primera posicion del array (suponemos i) y otra que apunte a la ultima posicion del array(suponemos j). Tras ello buscamos hacia adentro las soluciones que su suma de precios de el dinero que tenemos.
si precios
+ precios[j] == dinero
solucion
i++
j--
sino si precios + precios[j] < dinero
i++;
sino si precios + precios[j] > dinero
j--
Lo hacemos mientras i<j . Cada vez que encontremos una solucion, sustiuira a la anterior (para conseguir que la solucion obtenida sea el par con distancia minima).
Asi obtendremos la solucion correcta.
