Re: [ACM ] 136如何優化速度

看板C_and_CPP作者 (十三)時間15年前 (2009/02/20 20:31), 編輯推噓3(3推 0噓 1→)
留言4則, 2人參與, 最新討論串1/2 (看更多)
※ 引述《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
推
02/20 21:01, , 1F
不能重複 Set
02/20 21:01, 1F
→
02/20 21:02, , 2F
set<int>
02/20 21:02, 2F
推
02/20 21:22, , 3F
1,2,3,4,5,6,9,10,15,25, nu=3 size=10
02/20 21:22, 3F
推
02/20 21:35, , 4F
元PO你講的是443那題~
02/20 21:35, 4F
‣ 更多 bleed1979 的文章
文章代碼(AID): #19dgA4m- (C_and_CPP)
‣ 更多 bleed1979 的文章
文章代碼(AID): #19dgA4m- (C_and_CPP)