睡前脑袋不清楚... 前篇的推文不知道在写什麽鬼，请无视它Orz ※ 引述《Arton0306 (Ar藤)》之铭言： : 根据题目， : 令p_1 p_2 ... p_n为点， : 其坐标为x_1 x_2 ... x_n (x_1<=x_2...<=x_n) : 考虑任意两点p_i p_j, where i<=j : 则这两个点至少要 (j-i)*D/(2*V) 的时间才能分开，p_i往负方向走，p_j往正方向走 : 现在我们算出每一对至少要花的时间 : 取最大的那一对，令其时间为T : 也就是T代表"至少"要这麽多时间才可能到达状态A : 而我记得题目的答案就是T : 请问怎麽证明T不只是"至少"，而且还是刚刚好？！ 令 p_1 <= p_2 <= ... <= p_n 为每个点的座标，构造一组对T的解，即每个点p_i的 新位置q_i，并且: (1) |q_i-q_(i-1)| >=D 任两相邻点对间距>=D (2) |p_i-q_i| <= V*T 在时间T内是走得到的。 另外原po提到的 "每一对至少要花的时间" 最大值T，没想错的话是 T=max{ [(j-i)*D-(p_j-p_i)]/(2V) } for all i<j 应该要扣掉这两个点之间原本的距离吧? greedy构造解 q_1 < q_2 < ... < q_n，在时间和与前一点距离的限制下， 每个点尽量往左跑，所以: q_1 = p_1-V*T q_i = max{ q_(i-1) + D, p_i-V*T } for 2<=i<=n 证明 (1) |q_i-q_(i-1)| >=D 显然 q_i-q_(i-1) >= [q_(i-1) + D]-q_(i-1) = D (2) |p_i-q_i| <= V*T，分两部份讨论 "p_i>q_i": q_i >= p_i-V*T => |p_i-q_i| <= p_i - (p_i-V*T) <= V*T "p_i<q_i": 反证法，先假设 q_i > p_i + V*T。 令 k 为，使 q_i = q_j + (i-j)*D 的最小 j 值。根据 {q} 的选法 j 必存在， 且 q_i>p_i => q_i = q_(i-1) + D => k<i 其中必 q_k = p_k - V*T //否则 k-1 是更小的 j 使 q_i = q_j + (i-j)*D 那麽 (p_k - V*T) + (i-k)*D = q_i > p_i + V*T => [(i-k)*D - (p_i-p_k)]/(2V) > T 跟T的选法矛盾了，因此假设不成立，即 q_i <= p_i + V*T --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.250.122 ※ 编辑: seanwu 来自: 140.112.250.122 (11/14 09:30)