Subtask 1

• Ta sẽ thử đưa từng bạn vào một nhóm nào đó, và xét từng nhóm xem liệu có thỏa đề bài hay không.
• Vì có ~N~ bạn nên sẽ có tối đa ~N~ nhóm.
• Độ phức tạp: ~O(N^{N})~.

Subtask 2

• Nhận thấy rằng việc sắp xếp điểm số của các bạn học sinh ngay từ đầu sẽ không làm thay đổi kết quả.
• Sau khi sắp xếp lại, ta xét từng vị trí ~i~, nếu thỏa: ~a_{i+1} - a_i > D~ thì sẽ có thêm nhóm mới.
• Độ phức tạp: ~O(NlogN)~.

Subtask 3

• Tương tự Subtask 2, nhưng với ~M \neq 0~ thì các vị trí thỏa ~a_{i+1} - a_i > D~ thì số bạn cần thêm sẽ là: ~\frac{a_{i+1} - a_{i} - 1}{D}~.
• Chúng ta chỉ thêm được tối đa ~M~ bạn, nên sẽ ưu tiên chọn những vị trí cần ít bạn hơn.
• Độ phức tạp: ~O(NlogN)~.

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

const int max_n = 2e5 + 7;

int n, res = 1;
long long k, x, a[max_n];
priority_queue<long long, vector<long long>, greater<long long> > pq;

int main(){
    cin >> n >> k >> x;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n - 1; ++i){
        if(a[i + 1] - a[i] > x){
            ++res;
            long long d = (a[i + 1] - a[i]);
            pq.push((d - 1)/ x);
        }
    }
    while(!pq.empty())
    {
        long long cost = pq.top();
        pq.pop();
        if(k >= cost){
            k -= cost;
            --res;
        }
        else break;
    }
    cout << res;
    return 0;
}