二分答案

引入

洛谷 P1676 [USACO05FEB] Aggressive cows G

农夫约翰建造了一座有 \(n\) 间牛舍的小屋，牛舍排在一条直线上，第 \(i\) 间牛舍在 \(x_i\) 的位置，但是约翰的 \(m\) 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

普通算法

第一次看到这个题目——哇，这么复杂，什么最大的最小距离，还要求小于等于 \(m\)，怎么办呢？我们可以尝试转化一下，假如现在有一个答案 \(x\)，那么我们怎么判断 \(x\) 是否合法呢？直接用一个循环呗，看一下有多少小屋满足条件。

很显然，我们只需要暴力枚举所有可能的答案，判断是否能够满足条件。但是，这里的 \(x_i\) 较大，枚举需要花费很多的时间，而且判断一个解是 \(\mathcal O(n)\) 的，这下可就雪上加霜了。因此我们需要想出一个更优秀的算法，并尽可能地避免 \(x_i\) 的大小带来的影响。

二分算法

仔细观察题目，我们就可以发现当一个解 \(x\) 满足条件的时候，\(x-1,x-2,\cdots\) 等等小于 \(x\) 的解都可以满足条件，也就是说在满足于不满足当中有一条分界线，那么我们就可以用二分解决了。

对于一个解 \(x\)，我们判断一下是否满足，如果满足那么就记录答案，并将区间往右缩小，尝试更大的解；如果不行，就证明我们的 \(x\) 太大了，就把区间往左边缩小。

注意理解题意，我们需要输出 \(ans+1\) 而非 \(ans\)，而 \(l\) 在最后一次移动的时候移到了 \(ans+1\) 的位置，因此我们不需要记录 \(ans\)，而是直接输出 \(l\) 就行了。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int kMaxN = 1e5 + 5;

int a[kMaxN], n, m, l, r, ans;

bool C(int x) {
  int l = a[1], c = 1;
  for (int i = 2; i <= n; i++) {
    a[i] - l > x && (c++, l = a[i]);
  }
  return c >= m;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for (l = 1, r = 1e9; l <= r; ) {
    int m = l + r >> 1;
    if (C(m)) {
      ans = m, l = m + 1;
    } else {
      r = m - 1;
    }
  }
  cout << l << '\n';
  return 0;
}

评论