| [Home|Training|Problems|Contests|C Language] | [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 |