二分搜索+最大化最小值（POJ-2456）

今天药忘吃喽~ 2022-04-22 12:18 181阅读 0赞

原题链接： [http://poj.org/problem?id=2456][http_poj.org_problem_id_2456]

**题目描述：**

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**

**Hint**

**OUTPUT DETAILS: **  
  
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.   
  
Huge input data,scanf is recommended.

**题意：**

农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,…,xN (0 <= xi <= 1,000,000,000). 但其中的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，就会发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，求出最大的最小距离。  
**输入描述：**

多组测试样例   
第一行：空格分隔的两个整数N和C   
第二行——第N+1行：分别指出了xi的位置   
**输出 **  
每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。   
**样例输入 **  
5 3   
1   
2   
8   
4   
9   
**样例输出 **  
3

**解题分析：**

这是一个最大化最小值的问题。首先对隔间编号从小到大排序，则最小距离为0，最大距离不会超过两端的两头牛之间的距离。所以可以二分枚举最小值来求。若当前最小值为x，可以放下C头牛，就先让x变大再进行判断是否可以都放下；如果放不下，说明当前的x太大了，则使x变小然后再进行判断，直到求出一个最大的x。

**AC代码：**

#include<iostream> 
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const int maxn=100005;
    int a[maxn];
    int n,c;
    int judge(int m){
    	int last=0;
    	for(int i=1;i<c;i++){
    			int cur=last+1;
    			while(cur<n&&a[cur]-a[last]<m)cur++;
    			if(cur==n) return 0;
    			last=cur;
    	}
    	return 1;
    }
    
    int main(){
    	while(cin>>n>>c){
    		for(int i=0;i<n;i++) scanf("%d",&a[i]);
    		sort(a,a+n);
    		int l=0,r=INF,m;
    		
    		for(int i=0;i<100;i++){
    			m=l+(r-l)/2;
    			if(judge(m)) l=m;
    			else r=m;
    		}
    		cout<<l<<endl;
    	}
    	return 0;
    }

[http_poj.org_problem_id_2456]: http://poj.org/problem?id=2456