洛谷P1824 进击的奶牛 题解 二分答案

题目链接：https://www.luogu.com.cn/problem/P1824

题目大意：

本题相当于在 \(n\) 个数中选 \(c\) 个数，使得这 \(c\) 个数中相差最小的两个数之差尽可能地大。

解题思路：

我们首先可以给 \(a_1 \sim a_n\) 从小到大排一下序（这里有点贪心的思想，你会发现很多涉及贪心的问题在排序之后解决起来都会方便很多）。

然后我们可以开始设计一个 bool check(int x) 函数，用来判断：在任意相邻两个数之差都 \(\ge x\) 的情况下，是否能够选够 \(c\) 个数。

接着咱们就来判断 check(x) 能否成立：

首先，最优解 选 \(a_1\) 肯定没毛病，

假设有一个最优方案，第一个选的数是 \(a_2\)，第二个选的数是 \(a_5\)，即满足 \(a_5 - a_2 \ge x\)，那么 \(a_5 - a_1 \ge x\) 肯定也成立。

在选择了 \(a_1\) 的情况下，我们可以从 \(a_2\) 开始到 \(a_n\) 选剩下来的数，对应前 \(i\) 个数，我肯定是希望尽可能选最多数字，因为这样能够腾给后面的数字的空间就更大。

假设我上一个选择的数是 \(a_p\)，对于当前的 \(a_i\) ，若 \(a_i - a_p \ge x\)（相差 \(\ge x\) 了），就选择 \(a_i\)，同时更新 \(p\) 为 \(i\)（ \(p\) 时刻对应当前最后一个选的数的下标）。

在整个过程中统计一个一共选了多少个数即可，只要 \(\ge c\) 个，check(x) 函数就返回 true；否则，返回 false。

check函数代码：

bool check(int x) {
    int p = 1, cnt = 1; // p表示最近一个选择的点, cnt表示目前已选择的点数
    for (int i = 2; i <= n; i++) {
        if (a[i] - a[p] >= x) {
            p = i;
            cnt++;
        }
    }
    return cnt >= c; // 选够c个就返回true
}

有了 check 函数接下来就是二分答案了。

可以发现，存在一个最大的整数 \(x\)，从 \(1\) 到 \(x\) check 函数都会返回 true；从 \(x+1\) 开始 check 函数就都会返回 false 了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, c, a[maxn];

bool check(int x) {
    int p = 1, cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] - a[p] >= x) {
            p = i;
            cnt++;
        }
    }
    return cnt >= c;
}

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++)
        scanf("%d", a+i);
    sort(a+1, a+n+1);
    int l = 0, r = 1e9, res;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid))
            res = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d\n", res);
    return 0;
}