UVa 11935

http://uva.onlinejudge.org/external/119/11935.pdf

Supongamos que conocemos la capacidad mínima necesaria que debe tener el tanque, sea esta capacidad C, cumple la siguiente propiedad:

  1. toda capacidad c < C no es suficiente para llegar al destino
  2. toda capacidad c > C sera suficiente para llegar al destino.

Esta propiedad nos permite realizar una búsqueda binaria para encontrar el valor de C.

Comenzamos con una capacidad mínima de 0 y una máxima de 100000 es suficiente. En cada paso de la búsqueda binaria vamos a escoger el valor medio entre el máximo y el mínimo  y simular los eventos del viaje con esta capacidad. Si el resultado es que no alcanza, entonces podemos descartar todos los valores menores que el, y fijar la búsqueda entre el valor del medio y el mayor valor. Si encontramos que con esa capacidad es suficiente, entonces descartamos todos los valores mayores y fijamos la búsqueda entre el valor mínimo y el valor medio.

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