养竹鼠

百度松果周赛题

将m个竹鼠塞进n个位置确定的隔间，求相邻最近两个竹鼠的距离最大值，即，令最近的两个竹鼠相隔最远

遇到这种题一定要想到二分！只要能想到二分事情就会简单很多

大体思路是，二分搜索答案（最近的两个竹鼠相聚的距离），然后写一个贪心的验证

贪心的思路是，对于一个确定的距离，尽可能多的在已知的隔间中塞入竹鼠，然后比较可以塞入的竹鼠数量和已知数量m，如果大于等于则成功

#include<bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10, INF = 1 << 30;

int a[N], n, m;

bool check(int len)
{
    // 以len为最小间隔长度可不可以装下m只竹鼠
    int cnt = 0, pre = -INF;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] - pre >= len)
        {
            cnt++;
            pre = a[i];
        }
    }
    return cnt >= m;
}

int main( )
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sort(a + 1, a + n + 1);

    int L = 0, R = INF;
    while (L < R)
    {
        // 二分模板，修改R的时候mid要+1
        // 博客里整数二分那一节有详细介绍
        int mid = (L + R + 1) >> 1;
        if (check(mid))
            L = mid;
        else
            R = mid - 1;
    }
    // 这个模板好就好在没有L和R的问题，while结束后LR相等了
    cout << L << endl;
    return 0;
}