Distributing Ballot Box ( Busqueda binaria)

Este problema lo pueden encontrar en este liga: http://uva.onlinejudge.org/external/123/12390.html
 Al leerlo practicamente podemos suponer que se puede hacer con un interval tree, sacando glotonamente el mayor eh incrementarla el numero de cajas asignadas a esta ciuda`, pero cuando nos sentamos a analizar un poco mas, descubrimos que es mas sencillo utilizar una tecnica de busqueda binaria: Busqueda Binaria

  Pero como podemos saber que se puede resolver un problema con esta tecnica? bueno el objetivo del problema es Dado un numero de ciudades y el numero de votantes que se encuentra en ella , distribuir las casillas de vopacion de tal manera que si se distribullen los votantes de la mejor manera, el maximo numero de votantes en cualquier casilla sea el minimo posible ( minimizar el maximo de votantes por casilla).

  Para verlo como un problema de busqueda binaria y como se plantea en el post de busqueda binaria debe ser creciente o decreciente, aqui en este caso , si nosotros ponemos un limite de votantes ( en otras palabras , ninguna casilla debe tener mas de este numero de votantes) y distribuimos las casillas de tal manera que forcemos a que se cumpla este limite , si el limite se puede conseguir , podemos buscar un limite inferior, pero si no, tendremos que encontrar un limite mas grande.
Usando la busqueda binaria se puede hacer en log2 de 2000000 que son aproximadamenste como 22 operaciones, lo costoso es validar que el liminte se pueda alcansar o no , para esto solo hay que asignar las casillas, veamos como queda el codigo:

/* Autor: Rodrigo Burgos Dominguez */
#include "stdio.h"
#include "string.h"

#define MAXCITIES 500000
#define MAXPOPULATION 2000000

int numcities, numboxes;
int population[MAXCITIES + 1];

/* Este metodo solo regresa uno (1) si se puede obtener vopos menores o iguales al limite establesido (limit)
   cero (0) en otro caso    */
int isPossible( int limit, int remainboxes ){
  int x, denominador;
  for( x = 0; x < numcities; x++){
    /* ya que desde al inicio se eliminaron el numero de cajas necesarias 
         ( el numero de ciudades) solo nos queda el remanente este remanente debemos 
         distribuirlo, de tal manera que logremos bajar la cantidad de votantes sobre 
         una misma casilla, iniciamos con un denominador en 1 ( ya que ya tenemos un caja apartada 
         para cada ciudad, solo vamos incrementando las cajas para
    reducir el numero de votantes , hasta que sea menor o igual a nuestro limite */
    for( denominador = 1 ; 
         population[x] / denominador + ( (population[x] % denominador) > 0 ? 1 : 0 )  > limit; 
         denominador++);
    remainboxes -= ( denominador - 1 );
    if( remainboxes < 0) return 0;
  }
  return 1;
}

main(){
   int x, remainboxes, izq, der, sol, med;
   while( scanf("%d %d", &numcities, &numboxes) != EOF &&  ( numcitias != -1 || numboxes != -1 ) ){
     for( x = 0; x < numcities ; x++) scanf("%d", &population[ x ]);
     remainboxes = numboxes - numcities;
     sol = 500000;
     /*Busqueda Binaria */
     for( izq = 0, der = MAXPOPULATION + 1; izq <= der ;  ){
        med = (izq + der) / 2;
        if( isPossible( med, remainboxes ) ){
           sol = med;
           der = med - 1; 
        }else izq = med + 1;
     }
     printf("%d\n", sol);
   } 
   return 0;
}