欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

百练-2456-Aggressive cows

程序员文章站 2022-06-17 20:21:42
...

ACM模版

描述

百练-2456-Aggressive cows

题解

二分 + 贪心。水题。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 100002;
const int INF = 0x3f3f3f3f;

int N, C;
int x[MAXN];

bool check(int m)
{
    int last = 0;
    for (int i = 1; i < C; i++)
    {
        int cur = last + 1;
        while (cur < N && x[cur] - x[last] < m)
        {
            cur++;
        }
        if (cur == N)
        {
            return false;
        }
        last = cur;
    }

    return true;
}

int main()
{
    cin >> N >> C;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", x + i);
    }
    sort(x, x + N);

    int l = 0, r = INF, ans = 0;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (check(m))
        {
            ans = m;
            l = m + 1;
        }
        else
        {
            r = m;
        }
    }

    cout << ans << endl;

    return 0;
}