1.(1) d,6 (2) g,6 (3) h,5 (4) h,5 (5) b,2 2. 0 1 2 3 4 5 6 7 8 9 10 a 22 88 4 15 28 17 59 31 10 b 22 59 17 4 15 28 88 31 10 3. 1 2 3 4 5 6 7 8 9 taskid 2 7 1 3 5 8 0 12 6 penalty=w4+w10+w9+w11=23 4. a. T(n)=7T(n/2)+Θ(n) by master theorem T(n)=Θ(n^lg7) b.T(n)=McT(n/c)+Θ(n^2) T(n)=Θ(n^log Mc) c c.from B T(n)=Θ(n^log M3) 3 log M3 lg7 n 3 < n lgM3 ── < lg7 lg3 M3<2^(lg7lg3)=α α=2^(lg7lg3) 5. use divde and conquer partition the problem in to 2 small problem T(n)=2T(n/2)+Θ(n) =Θ(nlgn) 1.將座標依X座標排序，另外儲存Y座標排序資訊 2.找到X座標中位數M，將數列分成兩堆L,R 3.遞回找出L 跟R的最小距離，取較小者為d 4.檢查X座標在 M-d，到M+d之間的座標P 5.對每個P的Y座標yp 找出y坐標在yp+d跟yp-d之間的點Q，令d'=PQ 6.若d'<d d<- d' 7.return d step 1 O(nlogn) step2~7 T(n)=2T(n/2)+n =Θ(nlogn) so nearest pair prob. 可在O(nlogn)內找出 b. a.已知farthest pair 為一convex hull 中的兩個頂點。 若已知一convex hull，則可在O(n)時間內找出farthest pair b.找convex hull 1.找出一y坐標最小中，x坐標也最小的點p 2.求各點與p0所成向量依角度大小排序 3.令s為一空stack，push p0 p1 p2 4.for i=3~n while Pia 到 Pib 不為left turn do pop(s) end while push(Pi,s) end for a.O(n) b. 1 O(n) 2.O(nlogn) 3.O(1) 4.O(n) pop個數不超過n 因此得證 farthest pair 可在O(nlogn)時間被找到 6. 1.任挑一邊，將該邊的兩個點所連結的所有邊消除 2.重複一直到邊E為空。 step1. O(1) step.2 (M) 因此可在O(n+m)時間內完成 approximation 令C*為此問題最佳解，A為每次任選邊的集合 因為C*至少包含A中每個邊所cover的點 因此 |C*|>= |A| 又此漸進法每次選兩個點進入C，|C|=2|A| 因此可得知|C|=2|A| 因此|C|<=2|C*| 所以approximation=2 7. 好像是用suffix之類的方法解... 可是我不會...請高手解之~~ 歡迎來信推文回文討論 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.44.247.251 每次切中間，worstcase就是O(logn) 畫一個decision tree 第一個中點做根，然後左半的中點做左子，右半中點做右子，遞回 可畫出 balance 的 BST ，樹高最高不超過logn 原則上greedy的做，每次選擇delayline最小的，若是遇到相同的， 則選擇penalty較小的，然後把較大的送到stack。 最後再把stack倒出來就是答案。 不過其實會有問題是時間七會是空的，不過剛好8 9沒有collsion，所以不影響時間順序 題目只問schedulle沒問algo，所以我這樣解XD ※ 編輯: taitin 來自: 61.230.239.3 (02/02 22:54) ※ 編輯: taitin 來自: 61.230.239.3 (02/02 23:23) ※ 編輯: taitin 來自: 61.230.239.3 (02/02 23:34)