二分

• 题目大意：

有一条长度为L的河，起点位于0,终点位于L，有n块石头位于起点和终点之间，第i块的位于ai，现在至多在n块石头中移走m块石头，问如何移动使得剩下的石头中距离相邻最近的两块石头的距离最大。

• 思路分析：

  1.包括起点和终点一共n+2块石头，移动后相邻两块的最短距离为res，则res位与（0，L）之间，可以考虑二分res;


  2.假设存在求出res的方案，那么小于res的方案也一定存在，因为可以通过减少移走的石头数量来解决，所以res的取值 
  存在最大值保证len<=res的方案均存在，>res的方案不存在，满足二分的性质；


  3.难点就是如何找出当前得出res的方案，即判断保证最小距离为res的情况下，移走的石头数量是否<=m,

   这里可以贪心考虑：


  4.按照距离起到的由近到远的顺序遍历每块石头，从前往后扫描，并记一下上一块石头的位置，如果当前石头和上一
  块石头的距离小于 res，则将当前石头拿走。因为如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头.
  这样总共拿走的石头数量不变，所以当前选法也是一组最优解.(这里的证明参考了y总)


  5.如果当前石头和上一块石头的距离大于等于res，则将上一块石头更新成当前这块。

• 代码

  #include<iostream>
  #include<algorithm>
  #include<cstring>
  #include<queue>
  #include<cmath>
  using namespace std;
  const int N=5e4+10;
  int a[N];
  int L,n,m;
  bool check(int mid)
  {
      int last=0,cnt=0;
      for(int i=1;i<=n;i++){
          if(a[i]-last<mid) cnt++;
          else last=a[i];
      }
      return cnt<=m;
  }
  int main()
  {
      cin>>L>>n>>m;
      for(int i=1;i<=n;i++)
       scanf("%d",&a[i]);
      int l=0,r=L;
      while(l<r){
          int mid=(l+r+1)>>1;
          if(check(mid)) l=mid;
          else r=mid-1;
      }
      cout<<l<<endl;
      return 0;
  }