睡前腦袋不清楚... 前篇的推文不知道在寫什麼鬼，請無視它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)