/*最大的最小间距：二分策略
* 最大值问题-->判定性问题
* 判断间距为d是否可行
* 对间距d采取二分策略
*贪心+二分
*2456 poj Aggressive cows todo 结果
* */
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int arr[MAXN];//stalls 桩子 房间
bool Judge(int n,int m,int distance){
int current = arr[0];
int number = 1;
for(int i=1;i<n;++i){
if(arr[i] - current >= distance){
number++;
current = arr[i];
}
if(number == m) return true;
}
return false;
}
int main(){
int n,m;//n个房间 m头牛
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;++i) scanf("%d",&arr[i]);
sort(arr,arr+n);
int left = 1;//最小的间距为1
int right = arr[n-1] - arr[0];//最大间距
int middle;
while(left <= right){
middle = left + (right - left) /2;
if(Judge(n,m,middle)){
left = middle + 1;
}else{
right = middle - 1;
}
}
// printf("%d\n",middle); //Wrong Answer
printf("%d\n",right); //输出最小距离的最大值
// printf("%d\n",left - 1); //todo 最后为什么是right left-1
}
return 0;
}
/*
*贪心+二分
* 3104 Drying 北京大学POJ
*http://poj.org/submit?problem_id=3104
* */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 10;
int water[MAXN];
bool Judge(int n,int k,int time){
int sum = 0;
for(int i=0;i<n;++i){
if(water[i] > time){
sum += ceil((water[i] - time) * 1.0 / (k - 1)); //不是k ！！！ ceil向上取整 只能针对浮点数
//ceil 天花板 floor 木地板 #include <cmath>
if(sum > time) return false;
}
}
return true;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&water[i]);
}
int k;//烘干能力
scanf("%d",&k);
sort(water,water+n);
if(k == 1){
printf("%d",water[n-1]);
}else{
int left = 1;
int right = water[n-1];
while(left <= right){
int middle = left + (right - left)/2;
if(Judge(n,k,middle)){
right = middle - 1; //不同于公牛的地方
}else{
left = middle + 1;
}
}
//printf("%d\n",right + 1); //ok
printf("%d\n",left);//公牛返回right极大值 本题返回left极小值
}
return 0;
}
