[Login|Register]
Problems

Status

Rank

Problem 1214
乡村医院
Time Limit: 1000ms
Memory Limit: 65536kb
Description
在一条笔直的公路上分布着n个村庄,为了节省开支,我们将挑选其中至多m个村庄修建医院。各医院所在的村庄的村民可以在本村的医院接受服务,而其他村庄的村民则去最近的医院接受服务。如果某村庄与多家医院的距离相同,可以任选一个医院。
为了减轻村民们的负担,我们希望让村民去医院所要行走的最远距离最小化。
为了方便描述,不妨设这条公路与X坐标轴重合,这样我们就可以用X坐标表示村庄的位置。
例如下图中有5个村庄,我们将挑选至多2个村庄修建医院,方格上端的数字表示坐标。左图中村庄3和4中有医院,村庄1的村民需要行走2个单位距离才能到达最近的医院;右图村庄2和4中有医院,所有村民至多行走1个单位距离就能到达最近的医院。事实上右图的方案就是最优的。
Input
输入包含多组数据。
每组数据第一行为整数n和m,表示村庄的数量和医院数量的上限。输入保证1≤m≤n≤20000
第二行包含n个非负整数,表示每个村庄的坐标。输入保证坐标严格递增,并且坐标的值不超过109
输入以n=m=0结束,不要处理这组数据。
Output
对每组输入数据输出一个整数,表示最小的最远距离。
Sample Input
5 2
0 1 2 5 6
3 3
1 2 4
4 1
2 3 4 5
0 0
Sample Output
1
0
2
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.8ms with 1 query(s).