P1824 进击的奶牛

题目描述

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

5 3
1
2
8
4
9

输出 #1

3

【题解】
我根据自己的理解，写了一个好理解一点的版本，注释详尽，像我一样的蒟蒻应该也能看懂

二分答案很好想，主要难点是判定答案是否可行，即代码中的“check”函数

代码奉上：

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;
int A[1000010];
int n,c,a;
bool check(int x)//判断此答案是否可行 
{
    int num=0;
    int l=A[1];//l记录上一只牛的位置，开始时第一只牛一定在第一个牛栏 
    for(int i=2;i<=n;i++)//依次枚举每个牛栏 
    {
        if(A[i]-l<x) num++;//若此距离不满足当前答案，那么需要的牛栏数+1，即把当前牛放到下一个牛栏 
        else l=A[i];//否则就更新上一次的牛栏位置 ，即上一头牛放的位置 
        if(num>a) return false;// 若需要牛栏数大于最大牛栏数，此答案不可行 
    }
    return true;//反之，若需要牛栏数小于最大需要牛栏数，此答案可行
}
int main()
{ 
  scanf("%d%d",&n,&c);
  for(int i=1;i<=n;i++)
    scanf("%d",&A[i]);
  sort(A+1,A+n+1);//由于无序，需排序（sort默认从小到大，不用写规则） 
  a=n-c;//最大剩余牛栏数 
  int l=1;//二分的左界，从1开始，即可能情况的最小值 
  int r=A[n]-A[1];//二分右界，即可能情况的最大值 
  while(l+1<r)//若左<右，则继续二分答案 
  {
      int mid=(l+r)/2;//二分 两区间分别为l ~ mid    ，     mid ~ r;
      if(check(mid)) l=mid;//若此答案可行，从mid ~ r区间继续查找（更大答案），即修改左界l=mid 
      else r=mid;//反之，若此答案不可行，从l ~ mid区间查找（合理答案），即修改左界l=mid 
  }
  if(check(r)) printf("%d",r);//若可行解为右界，输出右界 
  else printf("%d",l);//若可行解为左界，输出左界 
  return 0;
}