作者Arton0306 (Ar藤)
看板Prob_Solve
標題[問題] 散開 間距 的證明
時間Mon Nov 12 21:50:39 2012
問題：(源自某一年的GCJ)
有n個點在實數線上
每個點都可以對應一個實數 值可以重覆
每個點都可以在線上以相同的速度V移動 所有點的移動速度都一樣
給定一個距離D 代表某一點要跟其它所有點至少相距D -- (A)
請問最快到達狀態A的時間需要多久？
這是原問題，但我想問一個證明
---------------------------------
根據題目，
令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不只是"至少"，而且還是剛剛好？！
-----------
整個題目可以想成
一堆學生橫的排成一列 現在要做體操 喊"一、二、散開" 大家就散開
每個學生的跑步速度都一樣
散開到左右2個人至少距離D，可以超過D，但不能小於D
差別在一開始的時候 題目中的點可以疊在一起
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.52.54
1F：推 seanwu:因為是取最大，T>="每一對至少要花的時間"，故T足夠(剛好) 11/14 01:49
2F：→ seanwu:抱歉上面那個推論有錯..應該說，你算的那個時間不只是 11/14 01:53
3F：→ seanwu:最少需要的時間..實際上那就是剛好需要那麼多，超過後恆>D 11/14 01:54
4F：→ seanwu:所以第一行推文是: T>="足夠每一對距離>=D的時間" 11/14 01:56