首页 > 代码库 > POJ 2456 Aggressive cows（二分搜索最大化最小值）

POJ 2456 Aggressive cows（二分搜索最大化最小值）

2024-07-24 10:48:17   225人阅读

Aggressive cows
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6372 Accepted: 3181

Description

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). 

His C (2 <= C <= N) cows don‘t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C 

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

题意：

有N个牛舍，第i个在Xi位置，同时有M头牛，将这M头牛放于牛舍中，使每头牛之间距离最大化。

思路：

因为无法直接确定每头牛的距离，我们可以考虑找到所有牛之间距离的最小值，利用二分从大到小搜索知道出现满足crt<N&&X[crt]-X[last]>d,此时的X[crt]-X[last]表示第crt个牛舍

与上一个可放置牛的牛舍距离，若大于d,则说明该crt或crt-1位置的牛舍处于临界点，可放置牛，若小于d则表示未达临界点，crt++,继续搜索。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const long MAXN=100000;
const long INF=1000000000;
long X[MAXN];
long N,M;
int Tdfs(long d)
{
	long last=0;
	for(int i=1;i<M;i++){
		long crt=last+1;
		while(crt<N&&X[crt]-X[last]<d){
			crt++;
		}
		if(crt==N)return 0;
		last=crt;
	}
	return 1;
}
int main()
{
	int i;
	long lb,ub,mid;
	while(cin>>N>>M)
	{
		lb=0,ub=INF;
		for(i=0;i<N;i++)
			cin>>X[i];
		sort(X,X+N);
		while(ub-lb>1){
			mid=(lb+ub)/2;
			if(Tdfs(mid))
				lb=mid;
			else
				ub=mid;
		}
		cout<<lb<<endl;
	}
	return 0;
}

本题不需使用long long或者_int64，long数据类型足以，long最大支持21亿+。另外注意失败条件“if(crt==N)return 0;”，当返回1时，lb=mid增大d值，反之减小d值。


POJ 2456 Aggressive cows（二分搜索最大化最小值）


联系
我们