Aggressive cows POJ 2456 二分

Aggressive cows POJ 2456

传送门：http://poj.org/problem?id=2456

Description

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

His C ( 2 < = C < = N ) C (2 <= C <= N) 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 1 1: Two space-separated integers: N and C

• Lines 2... N + 1 2...N+1 2...N+1: Line i + 1 i+1 i+1 contains an integer stall location x i x_i xi​

Output

• Line 1 1 1: One integer: the largest minimum distance

Sample Input	Sample Output
5 3 1 2 8 4 9	3

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

题意：
给出 n n n和 c c c，分别表示牛棚的位置和牛的数量，牛棚在 x x x轴上直线排列，接下来 n n n行给出每个牛棚的 x x x坐标(乱序) ， 现要把牛牛都单独放到一个牛棚里，问选择的牛棚之间的最小距离最大可以是多少。
思路：
假设 x x x是猜测的最小距离的最大值， s s s是真实的最小距离的最大值，那么对于所有可行的 x x x，都有 x < = s x<=s x<=s
且 f ( x ) = ( x < = s ? 1 : 0 ) f(x)=(x<=s?1:0) f(x)=(x<=s?1:0)具有单调性，所以可以二分找答案。
在 c h e c k check check函数中，我们模拟一遍放牛牛的过程，在每个与前一个放过牛的牛棚的间距大于等于 x x x的牛棚里放牛牛，最后如果放下的牛牛等于牛的数量，那么答案可行，否则不可行。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;
#define ll long long
#define rd(x) scanf("%lld",&x);
#define pn(x) printf("%lld",x);
const ll N = 1e5+9 ;
ll a[ N ] , n , c ;
bool check( ll d ){
    ll tot = 1 , now = a[ 1 ] ;
    for( int i = 2 ; i <= n ; i ++ ){
        if( a[ i ] - now < d ){ continue ; }
        else if( a[ i ] - now >= d ){
            now = a[ i ] ; tot ++ ;
        }
        if( tot >= c ) return 1 ;
    }
    if( tot < c ) return 0 ;
}
int main(){
    rd( n ) ; rd( c ) ;
    for( int i = 1 ; i <= n ; i ++ ) rd( a[ i ] ) ;
    sort( a+1 , a+1+n ) ;
    ll l , r , mid , ans = 0 ;
    l = 1 , r = 1e10+1e10 ;
    while( l < r ){
        mid = l+r >> 1 ;
        if( check( mid ) ) l = mid+1 , ans = mid ;
        else r = mid  ;
    }
    pn( ans ) ;
return 0 ;
}