推 chrisdar:不能重複 Set 02/20 21:01
→ chrisdar:set<int> 02/20 21:02
推 chrisdar:1,2,3,4,5,6,9,10,15,25, nu=3 size=10 02/20 21:22
推 Holocaust123:元PO你講的是443那題~ 02/20 21:35
※ 引述《Holocaust123 (Terry)》之銘言：
: ACM 第 136 題的題目：http://0rz.tw/au0f1
: 他先定義甚麼是ugly number，然後要找第1500個ugly number
: 所謂ugly number就是質因數分解之後的質因數只能有 2 或 3 或 5 的數。
: 2 跟 3 跟 5 可以出現 0 次，所以 1也算 ugly number。
: 一開始的前幾個ugly number是：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
: 然後題目是找出第 1500 個ugly number。
http://bleed1979.myweb.hinet.net/codes/v1/136.c
首先最好這個Collection一定要能丟進去就排序, 且不可重複
1我們稱為un(ugly number)先丟入, size = 1
再丟入2 * un, 3 * un, 5 * un
然後排序成1, 2, 3, 5, 此時un = 2, size = 4
再丟入2 * un, 3 * un, 5 * un
然後排序成1, 2, 3, 4, 5, 6, 10, 此時un = 3, size = 7
上面例子要找到4, index = 3, 要算到size = 7(index = 6)
因為插入的關係
所以要找1500個, 要算到size是1600個左右, 答案才會出現
類似題我做過的還有一題忘了題號, 該題是2, 3, 5, 7
方法是一樣的
Bleed
--
ACM's PARADISE
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.16.70