微软网站设计,中企建设网站,河海大学土木专业类建设网站,德源网站建设P1824 进击的奶牛
题目描述
Farmer John 建造了一个有 N N N#xff08; 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2≤N≤105) 个隔间的牛棚#xff0c;这些隔间分布在一条直线上#xff0c;坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1,x2,⋯,xN 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2≤N≤105) 个隔间的牛棚这些隔间分布在一条直线上坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1,x2,⋯,xN 0 ≤ x i ≤ 1 0 9 0 \leq x _ i \leq 10 ^ 9 0≤xi≤109。
他的 C C C 2 ≤ C ≤ N 2 \leq C \leq N 2≤C≤N头牛不满于隔间的位置分布它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗Farmer John 想把这些牛安置在指定的隔间所有牛中相邻两头的最近距离越大越好。那么这个最大的最近距离是多少呢
输入格式
第 1 1 1 行两个用空格隔开的数字 N N N 和 C C C。
第 2 ∼ N 1 2 \sim N1 2∼N1 行每行一个整数表示每个隔间的坐标。
输出格式
输出只有一行即相邻两头牛最大的最近距离。
输入输出样例 #1
输入 #1
5 3
1
2
8
4
9输出 #1
3题解
#include bits/stdc.h
using namespace std;
const int N 1e67;
int n, C, x, b;
int g[N], sum 1, ans, mid;
int main() {cinnC;for(int i1;in;i){cing[i];}sort(g1, gn1);int l g[1], r g[n];while(lr){sum 1;mid l(r-l)/2; int cow g[1];for(int j2;jn;j){if(g[j] - cow mid){sum;cow g[j];}}if(sumC) {ans mid;l mid 1;}else{r mid;}}coutansendl;return 0;
}
