题解 P1824 【进击的奶牛】

· · 题解

非常经典的一道二分答案模板题
什么是二分答案？简单地说，就是和二分查找相似，二分每个答案，然后对这个答案进行求证，看是否满足条件，然后再次进行左右区间查找，知道二分到单个点上
因为我太弱了，可能说的话有些逻辑错误或者表达不清qwq
这一题，我们二分答案找每个牛棚之间的最大距离。
先上代码： 

#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=-1;
int a[1000005];
bool check(int x){   //答案是否满足，满足返回1，反之返回0
    int now = 1, num = 1;
    for (int i = 2; i <= n; i++){
        if (a[i]-a[now]>=x){
            now=i;
            num++;
        }
    }
    return num>=m;
}
void merge(int l,int r){
    if(r-l<0) return;    //边界
    int mid=l+(r-l>>1);    //这样处理防止溢出
    if(check(mid)){   //如果满足，我们记录当前最大值，然后往左区间寻找答案
        merge(mid+1,r);
        ans=max(ans,mid);
    }
    else{  //如果不满足，就往右区间寻找
        merge(l,mid-1);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);  //注意，要排序处理。
    merge(1,(2<<30));
    printf("%d",ans);
}

二分答案的merge()都差不多，主要是check()

这里细讲本题check：

我们假设最大距离是x，将题目意思转变一下，就变成了这样：

在n个数中选取m个数，它们两两之间的距离大于等于x。

因为我们的数列是满足单调性质的，所以我们可以从第一个数往后找，看看有几个数满足a[i]-a[i-1]<=x;
如果数量大于m，则满足条件，反之亦然. 

bool check(int x){   
    int now = 1, num = 1;
    for (int i = 2; i <= n; i++){
        if (a[i]-a[now]>=x){
            now=i;
            num++;
        }
    }
    return num>=m;
}

几个要强调的：