洛谷 P1316 丢瓶盖——二分查找

Solution：

这是一道标准的考二分查找的题目。重点还是二分的范围，我们先将所有点的位置按从小到大排序。最大的距离应该是0~a[n]-a[1]之间。

#include<iostream>
#include<algorithm>
#define MAX 100005
using namespace std;

int n,m;
int a[MAX];
bool judge(int mid){
    int cnt=1,last=a[1];
    for(int i=2;i<=n;i++) {
        if(a[i]-last>mid){
          last=a[i];
          cnt++;
        }
    }
    if(cnt>=m){//说明距离小了，返回true
        return true;
    }else{//说明距离大了，返回false
        return false;
    }
}
int main() {
    cin>>n>>m;
    int left=0,right;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1,a+n+1);//排序
    right=a[n]-a[1];//right初始值
    while(left<=right){
        int mid =(left+right)/2;
        if(judge(mid)) left=mid+1;//
        else right=mid-1;
    }
    cout<<left;
    return 0;
}