首页 > 代码库 > POJ 2456 Aggressive cows(二分搜索最大化最小值)
POJ 2456 Aggressive cows(二分搜索最大化最小值)
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?
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
* 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(二分搜索最大化最小值)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。