Bài tập THT Bảng B 2021

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
constexpr int Inf = 1e9 + 7;
int n, m, c[N];

void Read()
{
    cin >> n >> m;

    for(int i = 1; i <= n; ++i)
        cin >> c[i];

    sort(c + 1, c + n + 1);
    c[0] = -Inf;

    if(c[n] == c[1])
    {
        cout << 0;
        exit(0);
    }
}

void Subtask_1()
{
    int l = 0, mid, h = c[n];

    function<int(int)> g = [&](int v)
    {
        int ans(0), x;

        for(int i = 1; i <= n; ++i)
        {
            if(c[i] - c[i - 1] > v)
                x = 1;
            else
                ++x;
            ans = max(ans, x);
        }

        return ans;
    };

    while(l <= h)
    {
        mid = (l + h) / 2;
        if(g(mid) < m)
            l = mid + 1;
        else
            h = mid - 1;
    }

    cout << l;
}

void Subtask_2()
{

    int l = 1, mid, h = c[n];

    function<ll(ll)> g = [&](ll v)
    {
        ll ans(1);

        for(int i = 2; i <= n; ++i)
            ans += max(0ll, (c[i] - c[i - 1] + v - 1) / v - 1) + 1;

        return ans;
    };

    while(l <= h)
    {
        mid = (l + h) / 2;
        if(g(mid) > m)
            l = mid + 1;
        else
            h = mid - 1;
    }

    cout << l;
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Read();
    if(m <= n)
        Subtask_1();
    else
        Subtask_2();
}