首页 > 其他 > 详细

POJ 2456 Aggressive cows

时间:2015-04-15 17:02:25      阅读:139      评论:0      收藏:0      [点我收藏+]
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;
#define maxn 100000

int n, m, x[maxn];
int Max;

bool judge(int d)
{
    int cnt = 1;
    int a = x[0];
    for(int i=1; i<n; i++)
    {
        if(a + d <= x[i])
        {
            a = x[i];
            cnt++;
        }
    }
    return cnt >= m ;
}

void solve()
{
    sort(x, x+n);
    int L = 0;
    int R = Max;
    while(L + 1 < R)
    {
        int mid = (L + R) >> 1;
        if(judge(mid)) L = mid;
        else R = mid;
    }
    cout<<L<<endl;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        Max = -1;
        for(int i=0; i<n; i++)
            {
                scanf("%d", &x[i]);
                Max = max(Max, x[i]);
            }

        solve();
    }
    return 0;
}

POJ 2456 Aggressive cows

原文:http://blog.csdn.net/dojintian/article/details/45061515

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!