Trovare altezza comune degli edifici con il costo minimo

Question

Questa è una domanda da qualche concorso di programmazione (non so esattamente a quale piano di programmazione appartenga, l'ho visto un anno fa). La domanda è la seguente:

ci sono N edifici, ognuno con la propria altezza (non necessariamente unico)

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

Dobbiamo fare tutti gli edifici della stessa altezza dire h.

Le operazioni consentite sono:

1. possiamo aggiungere un po 'di altezza per un edificio.
2. Siamo in grado di rimuovere un po 'di altezza da un edificio.

C'è un costo associato a ciascun edificio per rimuovere/aggiungere un'unità di altezza. Supponiamo che c (i) sia il costo per rimuovere/aggiungere un'altezza unitaria a un edificio. Il rispettivo costo sono i seguenti:

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

Supponendo che abbiamo un'altezza sufficiente (unità) a disposizione, dobbiamo trovare il costo minimo, che è necessario per rendere tutti gli edifici della stessa altezza.

Ingresso: Prima riga specificherà N il numero di edifici. (1 = N < = 100000). Second Line of Input sarà per l'altezza degli edifici.

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

Terza linea di ingresso darà la matrice costo

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

uscita

L'uscita sarà semplicemente il costo minimo richiesto.

ingresso del campione:

3 

2 1 3 

10 1000 1 

Esempio di output

12 

Spiegazione: Fare tutti gli edifici di altezza 1, quindi il costo sarà 10 * (2-1) + 1000 * (1-1) + 1 * (3-1) ie 12.

Conosco il metodo della forza bruta che è O (n^2).

Il metodo di forza bruta ho pensato è il seguente:

Qualunque sia la medesima altezza h sia, deve essere dal

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

cioè h deve essere uguale su qualsiasi h (i). Ora controllo per ogni h (i) Posso calcolare la risposta in O (n^2).

è possibile farlo più velocemente?

Answer 1

O (n log (n)) Soluzione:

Let h (i) denotano l'altezza dell'i-edificio e lascia che c (i) denoti il ​​costo dell'edificio ith.

1. Passaggio 1: ordinare l'edificio in base all'altitudine dei rispettivi edifici in ordine decrescente. Lascia che questa disposizione si chiami P. cioè P (1) è l'altezza dell'edificio più grande e P (n) è l'altezza dell'edificio più piccolo. Questo richiede O (n log n).
2. Step-2: somma tutte le altezze dell'edificio. Sia S questa somma. Questo passaggio richiede O (n) tempo. Step-3: Let Cost_of_Increase (i) denota il costo se facciamo altezze di tutti gli edifici che hanno un'altezza MENO rispetto all'edificio ith uguale all'altezza dell'edificio ith nell'ARRAY SORTED P, ovvero Cost_of_Increase (i) se realizziamo gli edifici P (i-1), P (i-2), ... P (n) uguale all'altezza dell'edificio P (i).

Ora utilizzare questa ricorsione:

Cost_of_Increase (i) = Cost_of_Increase (i-1) + (h (i) -h (i-1)) * (somma dei costi di P (i- 1) th building to P (n) th builing)

Si noti che nella ricorsione di cui sopra l'ordine di i e i-1 è secondo l'ordine di P, cioè l'ordine ordinato.

Ora deduciamo che Cost_of_decrease (i) denota il costo se realizziamo tutti gli edifici che hanno altezze MAGGIORE rispetto all'edificio ith uguale all'altezza del ith dell'edificio nell'ARRAY ORDINATO P, ovvero Cost_of_decrease (i) se facciamo il edifici P (1), P (2), ... P (i-2), P (i-1) pari all'altezza dell'edificio P (i).

Per questo utilizzo questo ricorsione:

Cost_of_decrease (i) = Cost_of_decrease (i + 1) + (h (i + 1) -h (i)) * (somma del costo di P (1) th costruzione di P (i-1) -esimo edificio)

costo Così totale per rendere l'altezza di tutti gli edifici pari a P (i) th edificio è:

Cost_of_Increase (i) + Cost_of_decrease (i).

Una volta ottenuto questo per tutti gli edifici, è sufficiente verificare quale è il costo più basso, e questa è la risposta.

Spero che aiuti!

Answer 2

Fare un ternary search o utilizzare un algoritmo hill climbing sull'altezza di tutti gli edifici dopo la fine dell'algoritmo. Per ogni altezza è possibile calcolare il costo in tempo lineare in modo che la complessità complessiva sia O (N * log (H)) dove H è la massima altezza risultante possibile.

EDIT: ecco un frammento di codice pseudo che dovrebbe funzionare per voi (questo è hill climbing simile approccio)

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; 
     } 
    } 
    ... 
    }