题目描述
陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？
输入输出格式
输入格式：
第一行，两个整数，A,B。（B<=A<=100000）
第二行，A个整数，分别为这A个瓶盖坐标。
输出格式：
仅一个整数，为所求答案。
输入输出样例
输入样例#1：
5 3
1 2 3 4 5
输出样例#1：
2
说明
限时3秒
【代码】：
#include<bits/stdc++.h>
const double eps = 1e-8;
const int maxn = 1e6+5;
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int n,k;
int a[maxn];
int check(int x)
{
int sum = 1;
int last = a[0];
for(int i=1;i<n;i++)
{
if(a[i]-last>x)
{
last=a[i];
sum++;
}
}
return sum>=k;
}
void solve(int l,int r)
{
int mid;
while(l<=r)
{
mid = (l+r)/2;
if(check(mid)) l=mid+1;
else r=mid-1;
}
printf("%d\n",l);
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
int l=0,r;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
r = a[n-1]-a[0];
solve(l,r);
}
}
/*
4 11
8.02
7.43
4.57
5.39
*/