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)