POJ 2456 Aggressive cows （二分、贪心）

本文主要是介绍POJ 2456 Aggressive cows （二分、贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=2456

题意：n个房子，m头牛，房子有一系列横坐标，问将m头牛塞进房子，每两头牛之间的最大间隔是多少。

二分+贪心。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6
using namespace std;
int n, m;
int pos[100100];
int check(int x) {int last = 0;int i;for(i = 1; i < m; i++) {int cur = last + 1;while(cur < n && pos[cur] - pos[last] < x) { //寻找下一个可以放的位置 cur++;}if(cur == n) return 0; //放不下 last = cur;}return 1;
}
int main() {scanf("%d %d", &n, &m);int i, maxn = 0;for(i = 0; i < n; i++) {scanf("%d", pos + i);maxn = max(maxn, pos[i]);}sort(pos, pos + n);int l = 0, r = maxn;while(r - l > 1) { //二分查找满足条件的解 int mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}printf("%d\n", l);return 0;
}

这篇关于POJ 2456 Aggressive cows （二分、贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---