#2157. 景区巴士
景区巴士
题目描述
A 景区是热门旅游景区,每天都有世界各地的游客前来游玩。
为了给游客提供便利,景区专门开通了从高铁站到景区的巴士。在暑假的某一天,有 N 名游客乘坐高铁来到当地的高铁站,并乘坐大巴去往景区,第 i 名游客到达高铁站的时间为 Ti。
景区有 C 辆大巴在高铁站等待运送游客,每辆大巴可以乘坐 X 名游客,大巴不允许超载,每辆大巴只能运送 ≤X 名游客。每辆大巴从高铁站接上游客开往景区后不会返回高铁站。
为了提升游客体验,当天景区准备了足够数量的大巴来运输游客,景区可以保证 C×X≥N,也就是说,所有的游客都能被大巴送到景区。如果某游客在 Ti 时刻到达高铁站,在时刻 Tj 他乘坐的景区巴士发车开往景区,他等待的时间为 Tj−Ti。
现要求优化开车时间,你可以指定每辆车的开车时间,但要使得所有游客中等待时间最长的游客,等待的时间最小。
请编程计算出所有游客中,等待时间最长的游客等待时间的最小值是多少?
输入
第 1 行输入 3 个整数 , , N,C,X。
第 2 行输入 N 个整数,代表每位游客到达高铁站的时间。
输出
输出一个整数,代表所有游客中,等待时间最长的游客等待时间的最小值。
样例
输入复制
8 3 3
0 2 8 5 4 15 10 18
输出复制
5
输入复制
9 3 3
0 2 8 5 4 15 10 18 20
输出复制
5
输入复制
15 6 3
28 29 35 36 46 0 2 9 5 4 15 10 18 21 25
输出复制
6
说明
样例 11 解释
在时刻 0,2,4 到达的 3 位游客乘坐在时刻 4 发车的巴士,这 3 位游客的最长等待时间为 4。
在时刻 5,8,10 到达的 3 位游客乘坐在时刻 10 发车的巴士,这 3 位游客的最长等待时间为 5。
在时刻 15,18 到达的 2 位游客乘坐在时刻 18 发车的巴士,这 2 位游客的最长等待时间为 3。
分析可知,这个方案,等待时刻最长的游客的等待时间是最小的。
数据范围
对于 10% 的数据,1≤N≤10。
对于 100% 的数据 1≤N≤105,0≤Ti≤109,1≤C≤105,1≤X≤N, C×X≥N。