「poj」 2456 Aggressive cows(二分)
程序员文章站
2024-03-16 08:56:40
...
题目链接:http://poj.org/problem?id=2456
题意:给出n个点,求其中m个点之间的最大的最小距离。
最大化最小值用二分比较多,这道题初始时就是0,就是,然后二分查找最大值。
AC代码:
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 1e5+100;
const int INF = 0x3f3f3f3f;
int n,m;
int a[maxn];
bool solve(int x){
int pos = 1,cnt = 1; //贪心思想第一只牛一定是在a[1]这个点,所以pos初始为1。
for(int i=2;i<=n;++i){
if(a[i] - a[pos] >= x){ //满足条件,更新pos
cnt++;
pos = i;
}
}
if(cnt >= m) return true; //可以放下m头牛
return false;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+1+n);
int l = 0,r = a[n] - a[1],mid;
while(l<=r){ //注意有等号
mid = (l+r)/2;
if(solve(mid)){ //[l,r]可以,试试[mid+1,r]行不行,找最大值
l = mid+1;
}
else r = mid-1; //缩小范围
}
printf("%d\n", l-1); /*这个可能太好理解,我自己是这么想得。
如果l==r时,solve(mid)为真那么l会加一,所以需要减一。
如果l==r时,solve(mid)为假,而又有l==mid,所以此时的l不合题意,应该是上一个状态的l合题,即l-1.*/
}
上一篇: Java对象与Avro相互转换
下一篇: 367. 有效的完全平方数