作者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