POJ2456 Aggressive cows贪心-二分策略

题目：http://poj.org/problem?id=2456

Aggressive cows

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 33659 Accepted: 15420

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

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.

Source

USACO 2005 February Gold

http://poj.org/problem?id=2456

C++代码：（根据王道机试指南贪心算法讲解视频）

//贪心策略 求牛的最小间距的最大化  采用贪心的二分策略 主要是要想明白牛与牛的间距怎么处理
//从之前的机制问题转化为判定性问题
//http://poj.org/problem?id=2456
//判定性函数
// 牛与牛之间的最小间距设置为distance n个房间 m头牛
//distance是后续需要二分的，一个个列举，可以看作是后需要处理的。但此时传入的参数是固定的，即要求最小距离是distance，要求牛与牛之间的间距要大于=distance
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN= 1e5+10; //10是安全距离
int arr[MAXN];//存放牛的位置的数组

bool Judge(int n,int m,int distance)
{
    int number=1;//记录放置的牛的个数，当number>=m时，说明在该距离下可以成功放置m头牛，满足要求
    //从第一个位置0开始放置  默认在第一个位置放 就是说此刻的current=1
    int current=arr[0];//记录当前牛放在哪个位置
    for(int i=1;i<n;i++)
    {
        if(arr[i]-current>=distance)//代表着这两个房间的间隔>+给定的位置，说明可以在arr[i]位置放牛
        {
            current=arr[i];//当前位置可以放牛
            number++;
        }
        if(number>=m)
        {
            return true;//牛可以放完 直接return true;
        }
    }
    return false;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d",&arr[i]);
        //二分策略寻找距离
        //先排序
        sort(arr,arr+n);
        int left=1;//牛与牛之间的最小间距为1
        int right= arr[n-1]-arr[0];//最大间距是最大隔间位置-最小隔间位置 distance[n-1]-distance[0]

        while(left<=right)
        {
             int mid=left+(right-left)/2;
             if(Judge(n,m,mid))//如果说当前的距离可行 可以试着让distance变大，去寻找最大化的 最小间距
                left=mid+1;
             else
                right=mid-1;
        }

        printf("%d",right);//求最小的最大化  最大是右边right 不断往left方向移动，直至不能移动
    }
    return 0;
}