POJ——2456题 Aggressive cows 二分搜索

Bertha 。 2022-02-16 03:51 193阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;24487</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;11369</td> 
  </tr> 
 </tbody> 
</table>

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

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.

二分搜索，每一次都判断是否能成立，直至左右夹击到正确答案

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #define INF 1000000000;
    using namespace std;
    int n,c;
    int x[100000];
    bool numx(int y){   //判断将y作为牛与牛之间的距离，所有的牛会不会放的下 
    	int last=0;    //定义的是上一头牛所处的的位置 
    	for(int i=1;i<c;i++){   //默认将第一头牛放在x[0]的位置 
    		int rod=last+1; 
    		while(rod<n&&x[rod]-x[last]<y){   //找到距离上一头牛所处位置长度超过y的第一个位置 
    			rod++;
    		}
    		if(rod==n)return false;  //若已经超过了最远的牛舍说明距离y是不可以实现的， 
    		last=rod;    //若找到了合适的位置，则更新最后一头牛的位置 
    	}
    	return true;  //若为超过最远牛舍的位置，说明此时每头牛之间距离为y是可以实现的 
    }
    int main()
    {
    	cin>>n>>c;
    	for(int i=0;i<n;i++){
    		cin>>x[i];
    	}
    	sort(x,x+n);   //将数组从小到大排序 
    	int left=0,right=INF;
    	while(right-left>1){
    		int mid=(right+left)/2;
    		if(numx(mid))left=mid;
    		else right=mid;
    	}
    	cout<<left<<endl;
    	return 0; 
    }