Re: [問題] 散開 間距 的證明
睡前腦袋不清楚... 前篇的推文不知道在寫什麼鬼，請無視它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)
推
11/14 09:52, , 1F
11/14 09:52, 1F
推
11/14 22:14, , 2F
11/14 22:14, 2F
討論串 (同標題文章)