进击的奶牛

暴力法 + 二分

#include<bits/stdc++.h>
using namespace std;
int n,c,x[100005];                        //牛棚数量，牛数量，牛棚坐标
bool check(int dis){                      //当牛之间距离最小为dis时，检查牛棚够不够
  int cnt=1, place=0;                     //第1头牛，放在第1个牛棚
  for (int i = 1; i < n; ++i){            //检查后面每个牛棚
    if (x[i] - x[place] >= dis){          //如果距离大于等于dis的位置有牛棚
      cnt++;                              //又放了一头牛
      place = i;                          //更新上一头牛的位置
    }
  }
  if (cnt >= c) return true;              //牛棚够
  else return false;                      //牛棚不够
  }
int main(){
  scanf("%d%d",&n, &c);
  for(int i=0;i<n;i++) scanf("%d",&x[i]);
  sort(x,x+n);                            //对牛棚的坐标排序
  int left=0, right=x[n-1]-x[0];          //right=1000000也行，因为是log2 n的
  int ans = 0;
  while(left < right){
    int mid = left + (right - left)/2;    //二分
    if(check(mid)){                       //当牛之间距离最小为mid时，牛棚够不够?
      ans = mid;                          //牛棚够，先记录mid
      left = mid + 1;                     //扩大距离
    }
    else right = mid;                     //牛棚不够，缩小距离
  }
  cout << ans;                            //打印答案
  return 0;
}

笔记：用二分法的时间复杂度是log(n)，就算数组长度达到1,000,000，二分法也只需要20次就可以，比遍历少了999,980次