题目描述 （二分经典题）

在一段定长区间内，将区间分为 $m$ 段，每段长度尽可能大。（分苹果）

时间复杂度

排序的 $O(n*log_n)$,二分的 $O(n*log_Q)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int q[N];

bool check(int mid)
{
    int count = 1; // count：合适的房子；无论mid取多少，第一个只牛都永远在第一个房子，即第一个房子永远是合适的
    int now = q[1]; 
    for (int i = 2; i <= n; i ++)
    {
        if (q[i] - now >= mid) 
        {
            count ++;
            now = q[i];            
        }
    }
    if (count >= m) return true; // mid满足条件，可以增大
    return false;
}

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

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

    int l = 1, r = q[n];
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;

    return 0;
}