USACO 进击的奶牛
题面
题目描述
Farmer John 建造了一个有 $N$($2 \leq N \leq 10 ^ 5$) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 $x _ 1, x _ 2, \cdots, x _ N$($0 \leq x _ i \leq 10 ^ 9$)。
他的 $C$($2 \leq C \leq N$)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John 想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
输入格式
第 $1$ 行:两个用空格隔开的数字 $N$ 和 $C$。
第 $2 \sim N+1$ 行:每行一个整数,表示每个隔间的坐标。
输出格式
输出只有一行,即相邻两头牛最大的最近距离。
样例 #1
样例输入 #1
1 | 5 3 |
样例输出 #1
1 | 3 |
题意
在坐标轴上有 n 个点,从中选取 m 个点,使得这m个点两两之间的最小距离最大。
看到使最小什么什么最大,直接二分,二分最小距离,$\tt Check$ 函数直接 $O(n)$ 过。水的不能再水了。
代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 祝馀宫!
评论