PKU1338-Ugly Numbers

題目：http://poj.org/problem?id=1338
所謂的Ugly Number就是那些質因數隻包含2,3,5的數
另外，1也算Ugly Number
多比詢問第n小的Ugly Number是多少？(1<=n<=1500)
(和2247幾乎一樣...只不過改成2,3,5,7)
程式碼：http://codepad.org/igGIZwhk
首先很直覺的想到不如把1...1500答案全部先造出來
但是怎麼樣讓這些數乖乖由小到大呢？
我們從"利用已知Ugly製造新的Ugly"這個角度來看(請連同參考程式碼)

很顯然的，Ugly*Ugly也會是Ugly、而且題目還很貼心的連1都算進去
那麼，
包含質因數2的Ugly有：2*Ugly[0]、2*Ugly[1]、2*Ugly[2]…
包含3有3*Ugly[0]、3*Ugly[1]、3*Ugly[2]…
包含5有5*Ugly[0]、5*Ugly[1]、5*Ugly[2]…
由於Ugly[]這個數組本身是由小到大
所以保證用這樣造出來的2U、3U、5U這三個序列也會由小到大

於是我們仿照MergeSort那種左序列右序列合併的做法
等同於將序列-2、序列-3、序列-5合併到Ugly[]的過程
並且注意一下是不是重複判斷掉
就能漂亮的求出答案

姊妹題2247只要多判斷一個序列-7就可以了

2011.12.16後記：
有天想說來google看看有沒有PKU上heap的題目
居然找到不少1338用heap的作法...
想想也罷，雖然浪費時間但這說明了
1338也是道可以測試heap、priority_queue(內建是max-heap，要自己改min-heap)的題目