题解 P1824 【进击的奶牛】

· · 题解

听着核爆神曲做的......

第一次读完题，十分想用搜索做，然而......

2<=N<=100,000 and 0<=xi<=1,000,000,000

我瞬间打消了用搜索的念头

还是按教科书上说的用二分来做吧

很显然的二分，数据如此大，一般都会想到贪心和二三四五六七分

其实我是想到什么算法就试一下过不过得了

显然易见的二分答案

二分枚举枚举答案 + 一个check函数了事

说的简单，但怎么check呢？？？？？？？？？？？？？？

check函数：

inline bool check(int k){
    int i=1,j,last=f[1],s=1;
    while(++i<=n&&s<c)
    if(f[i]>=last+k)s++,last=f[i];
    return s>=c;
}

注释：f已从小到大排序

解说：贪心思想，如果有（1，2，5）三个数，要求间隔为3，很显然选择1，5 而不是2和5虽然都可以

so last初始化f[1]

然后枚举后面的，只要f[i]>=last+间隔 个数++

最后return 个数>=牛的数量

程序拜拜

完整代码

#include<bits/stdc++.h> 
using namespace std;
int n,c,f[100100];
inline bool check(int k){
    int i=1,j,last=f[1],s=1;
    while(++i<=n&&s<c)
    if(f[i]>=last+k)s++,last=f[i];
    return s>=c;
}
int main( ){
    std::ios::sync_with_stdio(false);
    cin>>n>>c;
    int i,j,l=1000010000,r=-1,ans,mid;
    for(i=1;i<=n;i++)cin>>f[i];
    sort(f+1,f+n+1);
    l=f[1];r=f[n]-f[1];
    while(r-l>1){
        mid=(l+r)/2;
        if(check(mid))ans=l=mid;
        else r=mid;
    }
    cout<<ans<<endl;
}