【二分查找】进击的奶牛

题目

P1824 进击的奶牛

---

题目描述

Farmer John 建造了一个有 $N$($2$ $\le$ $N$ $\le$ $100000$) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 $x_1$ ,…,$x_N$
(0 $\le$ $x_i$ $\le$ $1000000000$)。

他的 $C$($2$ $\le$ $C$ $\le$ $N$) 头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 $1$ 行：两个用空格隔开的数字 $N$ 和 $C$。

第 $2$ ~ $N+1$ 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

样例 #1

样例输入 #1

5 3
1
2
8
4
9

样例输出 #1

3

解题

方法一：二分查找

思路

二分最大的最近距离（右边界）。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, c, lmt;
int a[N];

bool check(int m) {
    int cnt = 0, prev = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] - prev < m) {
            if (++cnt > lmt) return false;
        } else prev = a[i];
    }
    return cnt <= lmt;
}


int main() {
    scanf("%d%d", &n, &c);
    lmt = n - c;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    int l = INF, r = a[n - 1] - a[0];
    for (int i = 1; i < n; ++i) l = min(l, a[i] - a[i - 1]);
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (check(m)) l = m;
        else r = m - 1;
    }
    printf("%d\n", l);

    return 0;
}