Huffman code with the alphabet of size 3

Aaron
learning note
Published in
Aug 28, 2021

Keywords: greedy, Huffman Code

題目

Codeforces 884D: Boxes And Balls

給n個箱子以及n種顏色的球。起初所有的球都放在第一個箱子裡面,現在我們可以做一個操作,從某個箱子中取出所有的球(該操作的成本等取出球的數量),並把這些球分放到k個箱子中,問要經過幾次操作才可以讓每個箱子只有一種顏色的球。

其中每一次操作的k可以自行決定2或是3。

INPUT:
N = 4
Balls = 2 3 4 5
Output:
Cost = 19
step1: 從第一個箱子內挑出所有的球(14),並分成三堆(2+3),(4),(5)
step2: 從(2+3)那個箱子中挑出所有的球(5),進一步分成兩堆(2),(3)
總成本為14+5=19

分析

題目問的是從一個箱子出發,漸漸地做一些切割,用最低成本將球依顏色分割到n個箱子,但反過來說也可以視為n堆球,要想辦法合併成1堆,並且成本最低,如果這個角度想,若k等於2,其實就是標準的Huffman coding,但是今天k可以是2或3,該怎麼處理?

這題肯定跟Huffman脫不了關係,理想上應該可以視為k=3的Huffman coding,也就是一次合併三堆球。但是題目給的n未必能夠讓我們每次都合併3堆,但我們知道每次三堆合併總堆數就會減2,因此若n為偶數,就push一個0到堆中使他變成奇數,不但不影響成本,還能讓程式可以簡單每以三堆一數的方式取球。

程式碼

  • 時間複雜度:O(n*log(n))
  • 空間複雜度:O(n)

--

--

Aaron
learning note

Software engineer who is also an algorithm lover.