Angry Cows S

题目大意

有 个关键点，你要用 条长度为 的线段去完全覆盖这 个关键点
问， 的最小值是多少？

分析

很显然，对于 ，若 是一个可行的解，那么 一定也是一个可行的解
这满足二分答案的性质，所以是可以用二分答案的：

• 那么就可以二分 的大小
• 函数就贪心的找左断点
• 统计这种情况下需要多少条这样的线段
• 判定是否合法

然后在找端点的时候，对于已知的左端点和确定的线段长度，我们是可以很轻松的找到右端点的
那么下一个左端点就是第一个大于当前右端点的点了，这个可以手写一个二分查找来实现

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int x[maxn], n, k;

inline int found(int p)
{
    if (p > x[n]) return n + 1;
    int l(1), r(n), ans(n + 1);
    while (l <= r) {
        int mid((l + r) >> 1);
        if (x[mid] > p) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

inline bool Check(int R)
{
    int p(1), cnt(0);
    while (p <= n) {
        int np = found(x[p] + R * 2);
        ++cnt, p = np;
        if (cnt > k) return 0;
    }
    return cnt <= k;
}

int main()
{
    n = __read(), k = __read();
    if (k >= n) return puts(0) & 0;
    for (int i = 1; i <= n; ++i)
        x[i] = __read();

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

    int l(0), r(x[n] - x[1]), ans(0);
    while (l <= r) {
        int mid ((l + r) >> 1);
        if (Check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf ("%d\n", ans);
}