问题描述
问题分析
最大化最小值
也是通过二分来寻找解
不断来对mid进行判断
是否符合题意
判断是否符合时
可以想到把第一个牛放在第一个
之后选取相隔大于mid的牛舍
如果可以选取的牛舍大于C
说明mid可以选取
那么继续往大距离查找
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
| #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