长度无限长的公路上,小塔雇佣了n位工人来种树,每个点最多种一棵树。
从左向右数,工人所站的位置为a1,a2,...,an。已知每位工人都会将自己所在位置的右侧一段长度的区间种满树,且每位工人的种树区间长度相同。
现在小塔希望公路上至少有k棵树,为了节约成本,他希望每位工人种树的区间长度尽可能短,请你帮他求出,工人们的种树区间至少多长,从能使得公路被种上至少k棵树。
第一行输入两个正整数n,k(1≤n,k≤2×105),分别为表示工人的数量,以及小塔要求树的最少数量。
第二行输入n个正整数a1,a2,...,an(1≤ai≤2×105),表示每名工人的位置。
在一行输出一个整数,代表工人们最短的种树区间长度。
输入
3 6
1 2 5
输出
3
说明
每位工人种树的区间长度至少为3。
这样以来:
第一名工人种:1,2,3点的树。
第二名工人种:2,3,4点的树。
第三名工人种:5,6,7点的树。
由于每个位置最多种一棵树,因此共有:1,2,3,4,5,6,7这些点有树,满足至少k=6棵树
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.