¡He estado tratando de pensar desde HORAS sobre este problema de TopCoder y no he podido encontrar una solución que funcione perfectamente y he encontrado la que se muestra a continuación que es increíblemente bella!¿Por qué este código funciona para este problema de TopCoder?
Estoy tratando de entender cómo funciona esta solución para el sondeo dado? ¿Y cómo podría haberlo pensado originalmente? Después de leer la solución, pensé que era una variante de la codificación de Huffman, pero eso es todo lo que pude obtener. Estoy muy cautivado y me gustaría saber qué línea de pensamiento podría conducir a esta solución ..
aquí está el problema: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091
Fox Ciel tiene un montón de trabajo que hacer. La tarea consiste en algunas tareas mutuamente independientes. Las diferentes tareas pueden tomar diferentes cantidades de tiempo para completar. Te dan un int [] workCost. Para cada i, la tarea i-ésima tarda workCost [i] segundos en completarse. A ella le gustaría asistir a una fiesta y conocer a sus amigos, por lo tanto, ella quiere terminar todas las tareas lo más rápido posible.
El problema principal es que todos los zorros, incluido Ciel, realmente odian hacer la tarea . Cada zorro solo está dispuesto a hacer una de las tareas. Afortunadamente, Doraemon, un gato robótico del siglo 22, le dio a Fox Ciel un martillo partido : un artilugio mágico que puede dividir a cualquier zorro en dos zorros.
Se le otorga un int splitCost. Usar el martillo partido en un zorro es instantáneo. Una vez que se usa un martillo en un zorro, el zorro comienza a dividirse en . Después de splitCost segundos ella se convertirá en dos zorros: el zorro original y otro zorro completamente nuevo. Mientras un zorro se está partiendo, no está permitido volver a utilizar el martillo.
El trabajo en una tarea no se puede interrumpir: una vez que un zorro comienza a trabajar en una tarea, debe terminarla. No está permitido que múltiples zorros cooperen en la misma tarea. Un zorro no puede trabajar en una tarea mientras ella está siendo dividida usando el martillo. Es posible dividir el mismo zorro varias veces. Es posible dividir un zorro antes y después de ella resuelve una de las tareas.
Calcule y devuelva el menor tiempo posible para que las zorras puedan resolver todas las tareas .
y aquí está la solución que encontré en este 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();
}
}
¿La cola de prioridad devuelve el elemento max o el elemento min al sondear? – ElKamina
Mínimo. Las colas de prioridad se ordenan de menor a mayor elemento y conservan su clasificación en una inserción. – Charles
Esta respuesta parece incorrecta. Considera 'minTime (new int [] {1, 1, 1}, 5)'. Obviamente, lo correcto es no paralelizar ninguna de las tareas, de modo que se necesiten 3s. ¡Esta solución daría 11s! –