愤怒的牛//HYSBZ - 1734//二分_综合

愤怒的牛//HYSBZ - 1734//二分

题目

农夫 John 建造了一座很长的畜栏，它包括NN (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,…,xN (0 <= xi <= 1,000,000,000). 但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢

Input

Line 1: Two space-separated integers: N and C * Lines 2…N+1: Line i+1 contains an integer stall location, xi

第一行：空格分隔的两个整数N和C

第二行—第N+1行：i+1行指出了xi的位置

Output

Line 1: One integer: the largest minimum distance

第一行：一个整数，最大的最小值

Sample Input
5 3
1
2
8
4
9

Sample Output
3

把牛放在1，4，8这样最小距离是3

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1734

思路

二分查找合适的值，每个值代入检查是否正确。
检查时给牛分配确定数量的房间然后判断是否有多的牛

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 100009
#define INF 1e9 
using namespace std;int arr[MAX];
int n,c;bool judge(int temp){
    int first=0,end;for(int i=1;i<c;i++){
    end=first+1;while(end<n&&arr[end]-arr[first]<temp)end++;if(end==n) return false;first=end;}return true;
}
int main(){
    while(scanf("%d%d",&n,&c)!=EOF){
    for(int i=0;i<n;i++){
    cin>>arr[i];}sort(arr,arr+n);int l=0,r=INF,mid;while(r-l>1){
    mid=(l+r)/2;if(judge(mid))l=mid;else r=mid;}cout<<l<<endl;}return 0;
}

注意

注意二分判断条件避免死循环。