GitBook

这里写图片描述 这里写图片描述

最大化最小值 也是通过二分来寻找解 不断来对mid进行判断 是否符合题意

判断是否符合时 可以想到把第一个牛放在第一个 之后选取相隔大于mid的牛舍 如果可以选取的牛舍大于C 说明mid可以选取 那么继续往大距离查找

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100200];
int n,c;
bool judge(int m) {
	int last=0,cnt=1;
	for(int i=1; i<n; i++) {
		if(a[i]-a[last]>=m) {
			last=i;
			cnt++;
		}
	}
	if(cnt>=c)
		return true;
	else
		return false;
}
int main() {
	while(scanf("%d %d",&n,&c)!=EOF) {
		for(int i=0; i<n; i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		int r=a[n-1]-a[0],l=1;
		int mid,res;
		while(r>=l) {
			mid=(r+l)/2;
			if(judge(mid)) {
				res=mid;
				l=mid+1;
			} else
				r=mid-1;
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【POJ】[2456]Aggressive cows