Perché questo codice funziona per questo problema TopCoder?

Question

Ho cercato di pensare da ORE a questo problema con TopCoder e non sono riuscito a trovare una soluzione perfettamente funzionante e ho trovato quello indicato di seguito che è follemente usato!

Sto cercando di capire come funziona questa soluzione per il dato problema? E come avrei potuto pensarci inizialmente? Dopo aver letto la soluzione, ho pensato che fosse una variante della codifica di Huffman, ma è il massimo che ho potuto ottenere. Sono davvero affascinato e vorrei sapere quale linea di pensiero potrebbe portare a questa soluzione ..

Ecco il problema: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

Fox Ciel ha un sacco di compiti da fare. I compiti sono costituiti da alcune attività indipendenti tra loro . Compiti diversi possono richiedere diversi importi di tempo per il completamento. Ti viene data una [] workCost. Per ogni i, l'attività i-es richiede workCost [i] secondi per il completamento. Vorrebbe far partecipare una festa a e incontrare i suoi amici, quindi desidera completare tutte le attività il più rapidamente possibile.

Il problema principale è che tutti i volpi, incluso Ciel, odiano davvero fare i compiti . Ogni volpe è solo disposta a svolgere uno dei compiti. Fortunatamente, Doraemon, un gatto robotico del XXII secolo, diede a Fox Ciel un martello diviso : un aggeggio magico che può dividere qualsiasi volpe in due volpi.

Viene fornito un splitCost int. L'uso del martello diviso su una volpe è istantaneo. Una volta che un martello viene usato su una volpe, la volpe inizia a dividere . Dopo una frazione di secondi, si trasformerà in due volpi: la volpe originale e un'altra volpe completamente nuova. Mentre una volpe si divide, non è permesso usare di nuovo il martello su di lei.

Il lavoro su un'attività non può essere interrotto: una volta che una volpe inizia a lavorare su un'attività, deve terminarla. Non è consentito a più volpi di collaborare nello stesso compito. Una volpe non può lavorare su un'attività mentre lei è divisa usando il martello. È possibile dividere più volte la stessa volpe . È possibile dividere una volpe sia prima che dopo lei risolve una delle attività.

Calcola e restituisci il tempo minimo in cui le volpi possono risolvere tutte le attività.

Ed ecco la soluzione che ho trovato su questo link

import java.util.*; 

public class FoxAndDoraemon { 
    public int minTime(int[] workCost, int splitCost) { 
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 

    for(int i : workCost) pq.offer(i); 

    while(pq.size()>=2) { 
     int i = pq.poll(); 
     int j = pq.poll(); 
     pq.offer(Math.max(i, j) + splitCost); 
    } 
    return pq.poll(); 

    } 
} 

Answer 1

Prima di tutto fate realizzare il ragionamento dietro `max (i, j) + splitCost'. Non è vero? Fondamentalmente, se hai una volpe, la dividi in due ed esegui ogni attività in modo indipendente. Chiamiamo questo processo "fusione".

Supponiamo ora di avere tre lavori a, bec in modo che a> b> c. È possibile unire (unire (a, b), c) o unire (unire (a, c), b) o unire (unire (b, c), a). Fai i conti e puoi provare che la fusione (fusione (b, c), a) è meno tra questi tre.

È ora possibile utilizzare l'induzione per dimostrare che questa soluzione è valida per qualsiasi numero di lavori (non solo 3).

Answer 2

Sta costruendo un albero da zero.

L'algoritmo utilizza un fatto di base per funzionare: Se si rimuovono i due elementi più piccoli, il costo di calcolo dell'elemento più piccolo è sempre inferiore al costo del più piccolo successivo più uno split. (Vedi il post di ElKamina per una prova molto più approfondita per questo).

Quindi, se nella struttura sono presenti solo due elementi (ad esempio 4 e 2) e il costo di suddivisione è 4, il tempo minimo sarà sempre 8 (l'elemento più prossimo al più piccolo, più il costo della divisione.

Quindi, per costruire il nostro albero: diciamo che abbiamo ottenuto il workCost [1,3,4,5,7,8,9,10], e la nostra splitCost è 3.

Quindi, guardiamo i due elementi più piccoli: 1,3 Il "costo" del calcolo di questi è al minimo 6 (il numero più grande più il costo di uno split). Quindi reinserendo 6 nella coda, stai essenzialmente aggiungendo il sottostruttura:

6 
1 3 

Dove "altezza"/"costo" è 6 in totale. Ripetendo questo processo, costruirai un albero usando i sottoelementi più piccoli che puoi (sia una sottostruttura esistente, sia un nuovo compito non finito).

La soluzione alla fine simile a questa: (Dove S (X) è il costo della scissione più risolvere tutto sotto di esso)

    S(17) 
      S(13)  S(14) 
     S(10)  9 10  S(11) 
    S(6)  7   S(8)  8 
1  3     4 5 

Se si traccia a ritroso fino questo albero, è facile vedere come la formula risolta: il costo di 1 e 3 è S (6), 4 e 5 è S (8), quindi S (6) e 7 è S (10), 8 e S (8) è S (11), ecc.