POJ2456 Aggressive cows

Posted on | In |

有N个
牛棚在x轴上,已知他们的坐标.FJ有C只奶牛,每只都必须安排在一个牛棚里,一个牛棚只能容纳一只.但是他们会互相攻击,所以要求距离最近的两个牛棚间的距离最大.

2 <= N <= 100,000

0 <= xi <= 1,000,000,000

2 <= C <= N

1
2
3
4
5
6
逆向思维：
注意问题中的“最小最大”(“最大最小”),这是使用二分求解的重要标志.
最小最大
最小距离为x时,放置的总牛数大于等于C
找最大的yes(循环结束后的R)
一个建议：如果你自己也搞不清最后结果是L还是R，可以保存满足的答案
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
#include<iostream>
#include<cstring>
#include<algorithm>
int n,c; 
int a[100000];
using namespace std;

bool isValid(int dis){
	int last=0;
	for(int i=1;i<c;i++)
{int next=last+1;
while(next<n&&a[next]-a[last]<dis) next++;
if(next>=n) return false;
last=next;
}
return true;
}
int main(){
	cin>>n>>c;
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	sort(a,a+n);
	int ans=0,mid;
	int L=0,R=a[n-1]+1;
	while(L<=R){
		mid=(L+R)/2; 
		if(isValid(mid))  {
			ans=mid;
			L=mid+1; 
		}
		else{
			R=mid-1;
		}
	}
	cout<<ans<<endl;
	
	
	
	return 0;
}

image