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

[FRAXIS (喔喔)]

※ 引述《aoqq12 (阿任)》之銘言：
: http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_99_01.pdf
: 今天一直卡住= =  第五題
: 感覺上用dp能做出來   可是想半天  還是卡住
: 我是想說先將 x y z排序
: 然後 a[i]= k-xi
: 在到 y or z排序好的 找小於a[i]的數來做組合
: 不過好像很沒技術性....= ="
: 這該怎麼解= =" 才會比較有效率   有請高手解惑 orz

首先，令Z' = k - z, for all elements z in Z

這問題就變成要找x, y, z 使得 x + y = z, where x in X, y in Y, z in Z'

這步要花O(|Z|)的時間

第二步，把Y和Z'做排序，這步要花O(|Z| lg |Z| + |Y| lg |Y|)的時間

第三步 對一個在X中的元素x，產生Yx = y + x, for all elements y in Y

我們現在要找的就是Ya和Z'的共同元素，只要找到了就是有解，因為Yx和Z'

都是有序的，所以要找共同元素只需要O(|Z| + |Y|)的時間。

第四步 對所有在X中的元素x執行第三步，時間是O(|X|(|Z| + |Y|))。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
※ 編輯: FRAXIS          來自: 140.119.162.50       (01/09 11:08)
推 christianSK:這樣沒辦法保證X+Y 所形成的list是sorted的吧
→ FRAXIS:Y已經是sorted了..  把每一個元素都加上一個常數x
→ FRAXIS:應該還是Sorted的吧..
推 christianSK:X是一個list加上去之後 會打亂order
→ christianSK:我想了一下 就算Xsorted 還是有可能Yx是unsorted
推 christianSK:有點誤會了 XD"
推 christianSK:沒注意到一次造一個list Ya出來
→ christianSK:抱歉抱歉 :)
推 tetragramm:為什麼每次找共同元素都只需要O(|Z|+|Y|)呢?
推 christianSK:老實說我也還是不懂@@
→ sneak: 這樣沒辦法保證X+Y  https://daxiv.com