\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Greedy>}}\)

• Vị trí các số không ảnh hưởng tới kết quả nên mình sẽ sort mảng để tiện tính toán

• Với mỗi khoảng cách \(x\) giữa hai số liền kề nhau

Ta đếm xem có bao nhiêu số kề nhau phân biệt có thể được chọn mà khoảng cách hai số bé hơn hoặc bằng \(x\)

Nếu số lượng này lớn hơn hoặc bằng \(k\) thì ta nhận và trong các số thỏa mãn ta chọn số có giá trị bé nhất

\(\color{orange}{\text{Hint 2 <Binary-Search>}}\)

• Gọi mảng \(dis[]\) là các khoảng cách phân biệt và được sắp xếp, ta sẽ chặt nhị phân trên mảng này

• Vì khoảng cách trùng nhau sẽ đưa ra kết quả giống nhau, ta có thể lọc thành các phần tử phân biệt

Con trỏ (\(l\) init đầu mảng, \(r\) init cuối mảng, \(m = \frac{l + r}{2}\))

Điều kiện chạy (\(l <= r\))

Trường hợp \(x = dis[m]\) thỏa mãn

Giá trị tối ưu \(best = dis[m]\)

Mình cần tìm khoảng cách nhỏ nhất nên mình đưa con trỏ \(r\) xuống (khoảng cách lớn hơn \(dis[m]\) vẫn đúng nhưng không tối ưu)

Trường hợp \(x = dis[m]\) không thỏa mãn

Mình cần tìm khoảng cách nhỏ nhất nên mình đưa con trỏ \(l\) lên (khoảng cách bé hơn \(dis[m]\) sai)

\(\color{green}{\text{Preference __ Code }}\): Approach

\(^{^{\color{purple}{\text{Complexity : }} O()\ \color{purple}{\text{time}}\ ||\ O()\ \color{purple}{\text{memory}}}}\)

int n, k;
vector<int> a;
inline bool check(int lim) /// kiem tra
{
    int cnt = 0;
    for (int i = 0; i + 1 < n; ++i)
        if (a[i + 1] - a[i] <= lim)
            cnt++, i++;

    return cnt >= k; /// so cap chon duoc nhieu hon so luong can
}

int main()
{
    cin >> n >> k;

    a.resize(n);    
    for (int &x : a) cin >> x; /// nhan tung phan tu
    sort(all(a));              /// sap xep

    set<int> t; /// tap hop cac khoang cach phan biet sap xep tang dan
    for (int i = 0; i + 1 < n; ++i)
        t.insert(a[i + 1] - a[i]);

    vector<int> dis; /// dua cac khoang cach vao mang moi de chat nhi phan
    for (int x : t)
        dis.push_back(x);

    int best = dis.back(); /// gia tri toi uu
    for (int l = 0, r = dis.size() - 1; l <= r; ) /// binary-search
    {
        int m = l + (r - l) / 2;
        if (check(dis[m])) /// neu thoa man
        {
            best = dis[m]; /// cap nhat gia tri toi uu
            r = m - 1;     /// x > m van dung nhung khong toi uu
        }
        else               /// neu khong thoa man
            l = m + 1;     /// x < m se sai
    }

    cout << best; /// xuat ket qua
    return 0;
}