Aggressive cows POJ - 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
  3
  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.

思路：

和之前的青蛙那道题挺像的，二分暴力做；但是思路很重要；光说用二分做用二分做，等到自己做的时候就不知道怎么做了；首先排序，二分出来一个mid 然后用check函数判断此时的mid符合那种条件；check函数检查用mid作为最小值最多能够选择几个牲口槽；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<stdio.h>

using namespace std;
#define PI acos(-1.0)
typedef long long ll;
const int maxx=1e9+7;
#define INF 0x3f3f3f
int n,m;
int a[100005];
int f(int mid)
{
    int sum=0;
    int len=1;
    for(int i=1;i<n;i++)
    {
        if((sum+(a[i]-a[i-1]))<mid)
        {
            sum+=a[i]-a[i-1];
        }
        else{
            sum=0;
            len++;
        }
    }
    if(len<m) return false;
    return true;
}
int main()
{
    int i;
    while(~scanf("%d %d",&n,&m))
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int low=a[n-1]-a[0],high=a[n-1]-a[0];
        for(int i=1;i<n;i++)
        {
            low=min(low,a[i]-a[i-1]);
        }
        int mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(f(mid))
            {
                low=mid+1;
            }
            else high=mid-1;
        }
        printf("%d\n",high);
    }

    return 0;
}