我是靠谱客的博主 温柔猎豹,这篇文章主要介绍POJ2456 Aggressive cows 二分+判断,现在分享给大家,希望可以做个参考。

题目:http://poj.org/problem?id=2456
大致题意:给出N个数轴上的点的坐标,将C个点插入这N个点中,求C个点之间的距离的最小值的可能的最大值。(有一点绕。。。)
挺简单的题目,就是单纯的二分+判断
我们利用二分法枚举可能的答案k,则k的最小值为0,最大值为输入数据中坐标位置间的最大距离。
判断可行性的方法:将输入坐标先排序,每次判断k是否可行时,统计所给坐标能否放下(c-1)个距离为k的线段,注意这里是要求放下c-1个而不是c个,因为最后一只牛可以放在最后一个位置,而其后不需要留下距离k.

参考代码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio> //二分+判断 #include <algorithm> using namespace std; const int maxn=100000+10; int pos[maxn]; //存储位置信息 int c,n; //C头牛,N个位置 bool check(int k) //检查k是否可行 { int cnt=0; int last=0,cur=1; while(cur<n) { if(pos[cur]-pos[last]>=k) { cnt++; last=cur++; } else cur++; } if(cnt<c-1) return false; return true; } int main() { scanf("%d%d",&n,&c); for(int i=0;i<n;i++) scanf("%d",pos+i); sort(pos,pos+n); int l=0,r=pos[n-1]-pos[0]; int mid; while(l<=r) { mid=(l+r)/2; if(check(mid)) l=mid+1; else r=mid-1; } printf("%d",r); }

最后

以上就是温柔猎豹最近收集整理的关于POJ2456 Aggressive cows 二分+判断的全部内容,更多相关POJ2456内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(71)

评论列表共有 0 条评论

立即
投稿
返回
顶部