POJ 2456 Aggressive cows 跟 NYOJ 586 疯牛【二分枚举+贪心】

POJ 2456 Aggressive cows 和 NYOJ 586 疯牛【二分枚举+贪心】

原题连接：http://poj.org/problem?id=2456               http://acm.nyist.net/JudgeOnline/problem.php?pid=586  

题意：直接看nyoj 的汉化版，我们简化一下，其实就是 给一条直线上的n个点，让你随意选取c个点，然后使得这c个点两两之间的最小距离，如何选取这c个点使这个最小距离最大，输出最大的最小距离max。

思路：我开始毫不看数据范围的去写了个深搜的代码，结果你懂得……TLE！！搜了写大牛的结题报告，发现这个题 最好的方法是 二分+贪心，用二分枚举所有可能的max可能的取值复杂度long（n）。再用贪心判断是否可行复杂度L，总复杂度就是 Llong（n）；

AC代码：

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<time.h>
#include<stdlib.h>
using namespace std;
int P[200000];
int n,m;
bool greed(int k)
{
    int i,max=P[0],sum=0;
    for(i=1;i<n;i++)
    {
        if(P[i]-max>=k)
        {
            sum++;
            max=P[i];
        }
        if(sum>=m-1)
          {return true;}
    }
    return false;
}
void two_find()
{
    int x=0,y=P[n-1]-P[0],mid;
    while(x<=y)
    {
        mid=(x+y)/2;
        if(greed(mid))
           x=mid+1;
        else
           y=mid-1;
    }
    printf("%d\n",x-1);
}
int main()
{
    //freopen("g:\\1.txt","r",stdin);
    //freopen("g:\\2.txt","w",stdout);
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<n;i++)
            scanf("%d",&P[i]);
        sort(P,P+n);
        two_find();//二分枚举最大距离
    }
}