睡前脑袋不清楚... 前篇的推文不知道在写什么鬼，请无视它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