Encontrar altura común de edificios con un costo mínimo

Question

Esta es una pregunta de un concurso de programación (no sé exactamente a qué concurso de programación pertenece, lo vi hace un año). La pregunta es la siguiente:

hay N edificios, cada uno con su propia altura (no necesariamente único)

{h1,h2,h3,...,hn} 

Tenemos que hacer todos los edificios de la misma altura dicen h.

Las operaciones permitidas son:

1. podemos añadir un poco de altura a un edificio.
2. Podemos eliminar algo de altura de un edificio.

Hay un costo asociado con cada edificio para eliminar/agregar una altura de unidad. Supongamos que c (i) es el costo de eliminar/agregar una altura de unidad a un edificio. El costo correspondiente son los siguientes:

{c1,c2,c3,...,cn} 

Suponiendo que tenemos suficiente altura (unidad) disponibles, tenemos que encontrar el costo mínimo que se requiere para hacer que todos los edificios de la misma altura.

Entrada: First Line especificará N el número de edificios. (1 < = N < = 100000). La segunda línea de entrada será para la altura de los edificios.

{h1,h2,h3,...,hn} 

Tercera línea de entrada dará la matriz de costo

{c1,c2,c3.....,cn} 

salida

La salida será simplemente el costo min requiere.

Ejemplo de entrada:

3 

2 1 3 

10 1000 1 

Muestra de salida

12 

Explicación: Hacer que todos los edificios de altura 1, por lo que el costo será 10 * (2-1) + 1000 * (1-1) + 1 * (3-1) es decir 12.

Conozco el método de fuerza bruta que es O (n^2).

El método de fuerza bruta que pensé es como sigue:

Cualquiera que sea la altura común h sea, debe ser de la

{h1,h2,h3,....,hn} 

es decir, h debe ser igual a cualquiera de h (i). Ahora comprobando cada h (i) puedo calcular la respuesta en O (n^2).

¿es posible hacerlo más rápido?

Answer 1

O (n log (n)) Solución:

Let h (i) denota la altura del i-ésimo edificio y que c (i) denote el costo del i-ésimo edificio.

1. Paso-1: Clasifique el edificio de acuerdo con las alturas de los edificios respectivos en orden decreciente. Permita que esta disposición se llame P., es decir, P (1) es la altura del edificio más grande y P (n) es la altura del edificio más pequeño. Esto toma O (n log n).
2. Paso-2: Sume todas las alturas del edificio. Deje S denotar esta suma. Este paso toma O (n) tiempo.
3. Paso-3: Deje que Cost_of_Increase (i) denote el Costo si hacemos que las alturas de todos los edificios que tienen alturas MENOS que el i-ésimo edificio sean iguales a la altura del i-ésimo edificio en el P ARRUITO CLASIFICADO, es decir, Costo_de_Incremento (i) si hacemos que los edificios P ​​(i-1), P (i-2), ... P (n) sean iguales a la altura del edificio P (i) th.

Ahora utilizar esta recursión:

Cost_of_Increase (i) = Cost_of_Increase (i-1) + (h (i) -h (i-1)) * (suma de los costes de P (i- 1) th edificio a P (n) th builing)

Tenga en cuenta que en la recursividad anterior el orden de i y i-1 es según el orden de P, es decir, el orden ordenado.

Ahora deje Cost_of_decrease (i) denotar el costo si hacemos que todos los edificios que tienen alturas MAYORES que el i-ésimo edificio sean iguales a la altura del i-ésimo edificio en el ARRAY PEDIDO, es decir, Cost_of_decrease (i) si hacemos el edificios P ​​(1), P (2), ... P (i-2), P (i-1) igual a la altura del edificio P (i) th.

Para este uso esta recursión:

Cost_of_decrease (i) = Cost_of_decrease (i + 1) + (h (i + 1) -H (i)) * (suma del coste de P (1) -ésimo edificio a P (i-1) -ésimo edificio)

coste tan total para la fabricación de la altura de todos los edificios igual a P (i) -ésimo edificio es:

Cost_of_Increase (i) + Cost_of_decrease (i).

Una vez que tenemos esto para todos los edificios, simplemente verifique cuál es el costo más bajo, y esa es la respuesta.

Espero que ayude!

Answer 2

Haz un ternary search o usa un algoritmo hill climbing en la altura de todos los edificios después del final del algoritmo. Para cada altura, puede calcular el costo en tiempo lineal, por lo que la complejidad general será O (N * log (H)) donde H es la altura resultante máxima posible.

EDIT: aquí es un fragmento de código de seudo que debería funcionar para usted (esto está subiendo como la colina enfoque)

typedef long long ll; 
    ll get_cost(int h) { 
    if (h < 0 || h > MAX_HEIGHT) { 
     return MAX_VAL; // some unreachable positive value 
    } 
    ... 
    } 


    int main() { 
    ... 
    int current = 0; 
    int leftp, rightp; 
    ll cv, lv, rv; 
    ll step = SOME_BIG_ENOUGH_VALUE; 
    while (step > 0) { 
     leftp = current - step; 
     rightp = current + step; 
     cv = get_cost(current); 
     lv = get_cost(leftp); 
     rv = get_cost(rightp); 
     if (cv <= rv && cv <= lv) { 
     step /= 2; 
     } else if (lv < rv) { 
     current = leftp; 
     } else { 
     current = rightp; 
     } 
    } 
    ... 
    }