POJ 2456 Aggressive cows（贪心 + 二分）

原题链接：Aggressive cows

题目大意：农夫 $John$ 建造了一座很长的畜栏，它包括 $N (2 <= N <= 100,000)$ 个隔间，这些小隔间依次编号为 $x_{1},...,x_{n} (0 <= x_{i} <=1,000,000,000)$ . 但是， $John$ 的 $C (2 <= C <= N)$ 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。 $John$ 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？

题目分析：题意想要表达的是 把 $C$ 头牛放到 $N$ 个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。这是一个典型的最小值最大化问题。先对畜栏编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为 $0$ 。所以我们可以通过二分枚举最小值来求。假设当前的最小值为 $x$ ，如果判断出最小差值为 $x$ 时可以放下 $C$ 头牛，说明当前的 $x$ 有点小，就先让 $x$ 变大再判断；如果放不下，说明当前的 $x$ 太大了，就先让 $x$ 变小然后再进行判断。直到求出一个最大的 $x$ 就是最终的答案。

代码如下：（PS：输入输出用 $printf()\, \,\,scanf()$ ）

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 100005;

int num[MAX];

int n, c;

bool tanxin(int x) {   // 判断 x 时，是否可以放得下 c 头牛

	int cnt = 1, temp = num[0];

	for (int i = 1; i < n; i++) {

		if (num[i] - temp >= x) {

			cnt++;

			temp = num[i];

			if (cnt == c) return true;

		}

	}

	return false;

}

void erfen() {   // 通过二分枚举最小值

	int left = 0, right = num[n - 1] - num[0];

	while (left <= right) {

		int mid = (left + right) / 2;

		if (tanxin(mid)) left = mid + 1;

		else right = mid - 1;

	}

	printf("%d\n", left - 1);

}

int main() {

	scanf("%d %d", &n, &c);

	for (int i = 0; i < n; i++)

		scanf("%d", &num[i]);

	sort(num, num+n);

	erfen();	

	return 0;

}

巴特西

POJ 2456 Aggressive cows（贪心 + 二分）

最新文章

热门文章