Re: [理工] [algo] 99中央第5題

看板Grad-ProbAsk作者christianSK (AG)時間15年前 (2011/01/08 23:54)推噓6(6推 0噓 9→)

留言15則, 4人參與討論串3/4 (看更多)

※ 引述《tetragramm (4Jay)》之銘言： : 獻醜了，提供一個簡單的想法 : 就像C大推文中所說的，先sort可以有降低複雜度的效果 : 首先一樣用暴力法在 X 和 Y 集合中找到x 和 y，所需時間為θ(n^2) : 因此就能夠知道z = k - x - y的值 : 用這個值在 Z 集合中做binary search看看能不能找到即可 : 每一次做binary search的時間複雜度為logn : 因此最後時間複雜度為θ(n^2 log n) : 有錯請指正 t大要求的話我就獻醜了 :) 正如我前面推文說的這是ACM來的為什麼我知道呢? 因為這是我去年某堂課的hw (不過我不是中央的) 所以這方法其實也是老師上課提到的要找 x,y,z, 使得 x + y + z = k 等同於找 x,y,z 使得 x + y = k - z 我只需要去比較 x + y , k - z 兩個list看是否有相同元素就可以了 (i) constrcut 這兩個list θ(|X|*|Y|) , θ(|Z|) (ii) 對這兩個list做 q-sort θ(|X|*|Y|*log(|X||Y|)) , θ(|Z|*log(|Z|)) (iii) 最後就是比較, 用Binary search來做, 我想應該是 θ( log ( |X|*|Y| ) * |Z| ) ( 請允許我假設|Z| < |X|*|Y| XD" ) 希望我想的沒錯~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.243.147.23

推

aoqq12

01/09 00:03, , 1^F

01/09 00:03, 1^F

→

christianSK

01/09 00:03, , 2^F

01/09 00:03, 2^F

推

tetragramm

01/09 00:12, , 3^F

01/09 00:12, 3^F