Почему этот код работает для этой проблемы TopCoder?

Я ЧАСОВ пытался обдумать эту проблему TopCoder и не мог найти идеально работающее решение, и нашел приведенное ниже, которое безумно красиво используется!

Я пытаюсь понять, как это решение работает для данной проблемы? И как я мог изначально подумать об этом? Прочитав решение, я понял, что это вариант кодирования Хаффмана, но это все, что я мог получить. Я действительно в восторге и хотел бы знать, какой ход мыслей может привести к этому решению.

Вот проблема: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091< /а>

У Фокса Сиэля много домашней работы. Домашнее задание состоит из нескольких независимых друг от друга заданий. Для выполнения разных задач может потребоваться разное количество времени. Вам дается int[] workCost. Для каждого i i-я задача требует workCost[i] секунд для завершения. Она хотела бы посетить вечеринку и встретиться с друзьями, поэтому она хочет выполнить все задания как можно быстрее.

Главная проблема в том, что все лисы, включая Сиэля, очень ненавидят делать домашнюю работу. Каждая лиса готова выполнить только одно из заданий. К счастью, Дораэмон, робот-кот из 22-го века, дал Фоксу Сиэлю расколотый молот: волшебное устройство, которое может разделить любую лису на двух лисиц.

Вам дается int splitCost. Использование раздельного молота на лисе происходит мгновенно. Как только молот используется на лисе, лиса начинает раскалываться. Через splitCost секунд она превратится в двух лисиц — изначальную лису и еще одну совершенно новую лису. Пока лиса раскалывается, нельзя снова использовать на ней молот.

Работу над заданием нельзя прерывать: как только лиса начала работать над заданием, она должна его закончить. Не допускается, чтобы несколько лис выполняли одну и ту же задачу совместно. Лиса не может работать над задачей, пока ее раскалывают молотком. Одну и ту же лису можно разделить несколько раз. Разделить лису можно как до, так и после того, как она решит одну из задач.

Вычислите и верните наименьшее количество времени, за которое лисы смогут решить все задачи.

И вот решение, которое я нашел по этой ссылке.

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(); 

  } 
}

java algorithm huffman-code
person GrowinMan    schedule 27.04.2012    source источник
comment
Возвращает ли приоритетная очередь элемент max или min при опросе?   -  person ElKamina    schedule 27.04.2012
comment
Наименее. Очереди с приоритетом сортируются от наименьшего к наибольшему элементу и сохраняют свою сортировку при вставке.   -  person Charles    schedule 27.04.2012
comment
Этот ответ кажется неверным. Рассмотрим minTime(new int[] {1, 1, 1}, 5). Очевидно, правильно было бы не распараллеливать ни одну из задач, чтобы это заняло 3 секунды. Это решение даст 11 секунд!   -  person Russell Zahniser    schedule 27.04.2012
comment
@RussellZahniser Каждая лиса будет выполнять только одну работу. Вы не можете заставить его выполнять 3 задания последовательно. «Каждая лиса готова выполнить только одно из заданий»   -  person ElKamina    schedule 27.04.2012

Ответы (2)


arrow_upward
6
arrow_downward

Прежде всего, вы понимаете, что стоит за `max(i, j) + splitCost'. Не так ли? По сути, если у вас есть одна лиса, вы разделяете ее на две части и выполняете каждую задачу независимо. Назовем этот процесс «слиянием».

Теперь предположим, что у нас есть три работы a, b и c, такие что a>b>c. Вы можете выполнить слияние (слияние (a, b), c), слияние (слияние (a, c), b) или слияние (слияние (b, c), a). Сделайте математику, и вы сможете доказать, что слияние (слияние (b, c), a) является наименьшим среди этих трех.

Теперь вы можете использовать индукцию, чтобы доказать, что это решение справедливо для любого количества заданий (не только для 3).

person ElKamina    schedule 27.04.2012

arrow_upward
3
arrow_downward

Это строительство дерева с нуля.

Алгоритм использует для работы один основной факт: если вы удалите два наименьших элемента, стоимость вычисления наименьшего элемента всегда будет меньше, чем стоимость следующего наименьшего элемента плюс разбиение. (См. сообщение ElKamina для более подробного доказательства этого).

Таким образом, если в вашем дереве было только два элемента (скажем, 4 и 2), а стоимость разделения была равна 4, наименьшее количество времени всегда будет равно 8 (следующий за наименьшим элементом плюс стоимость разделения).

Итак, для построения нашего дерева: допустим, мы получили workCost [1,3,4,5,7,8,9,10], а наша splitCost равна 3.

Итак, смотрим на два самых маленьких элемента: 1,3. «Стоимость» их вычисления составляет минимум 6 (наибольшее число плюс стоимость разделения. Затем повторно вставляя 6 в очередь, вы, по сути, добавляете поддерево:

  6
1   3

Где "высота"/"стоимость" всего 6. Повторяя этот процесс, вы построите дерево, используя наименьшие возможные подэлементы (либо существующее поддерево, либо новое незавершенное домашнее задание).

В конечном итоге решение будет выглядеть так: (где S(X) — это стоимость разделения плюс решение всего, что находится под ним)

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

Если вы проследите это дерево в обратном направлении, то легко увидите, как его решает формула: стоимость 1 и 3 равна S(6), 4 и 5 равна S(8), затем S(6) и 7 равна S(10). ), 8 и S(8) есть S(11) и т. д.

person Charles    schedule 27.04.2012