Problem : 131 - 野心勃勃的乳牛

Problem Statistics

Solved Member: 34　　Submission: 58　　User Tried: 36

Statement:

Farmer John建立了新的農場，一共有(2<=N<=100000)個牛欄。
這些牛欄座落在一條直線上的位置X1,X2,...,XN上(0<=Xi<=1000000000)，每個牛欄最多只能住一隻牛，並且每隻牛都必須有地方住。
而他的(2<=C<=N)隻牛不喜歡這個新農場，想要和牠最靠近的牛打架
為了防止牠們互相傷害，FJ適當的把牛分配進去，使得任兩個牛之間的最近距離盡可能的大。問最大可能的這個距離是多少？

Input:Output:

第一行有N,C兩個正整數以空格隔開，意義如題敘

緊接著N行每行有一個整數，代表X1,X2,...,XN

輸出最近乳牛之間可能的最大距離，好讓牠們幹架的可能性最小化

Sample Input:Sample Output:

5 3
1
2
8
4
9

Source:

USACO 2005 Feb. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65535kb
1	1000ms	65536kb	5
2	1000ms	65536kb	5
3	1000ms	65536kb	5
4	1000ms	65536kb	5
5	1000ms	65536kb	5
6	1000ms	65536kb	5
7	1000ms	65536kb	5
8	1000ms	65536kb	5
9	1000ms	65536kb	5
10	1000ms	65536kb	5
11	1000ms	65536kb	5
12	1000ms	65536kb	5
13	1000ms	65536kb	5
14	1000ms	65536kb	5
15	1000ms	65536kb	5
16	1000ms	65536kb	5
17	1000ms	65536kb	5
18	1000ms	65536kb	5
19	1000ms	65536kb	5
20	1000ms	65536kb	5