[問題] 散開 間距 的證明
看板Prob_Solve (計算數學 Problem Solving)作者Arton0306 (Ar藤)時間12年前 (2012/11/12 21:50)推噓1(1推 0噓 3→)留言4則, 1人參與討論串1/2 (看更多)
問題：(源自某一年的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
推
11/14 01:49, , 1F
11/14 01:49, 1F
→
11/14 01:53, , 2F
11/14 01:53, 2F
→
11/14 01:54, , 3F
11/14 01:54, 3F
→
11/14 01:56, , 4F
11/14 01:56, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
