Codeforces Round #727 (Div. 2)C. Stable Groups

给一个数组, 求加入n个数字(大小不限)后, 使得数组中两个的差不大于k. 求n是多少.

这题贪心, 就是每次都取加入最大的数字.

#include "bits/stdc++.h"
using namespace std;   
#define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main() { 
    fr;
    int64_t N,K,X;
    cin >> N >> K >> X;
    int64_t A[N + 1];
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i];
    }
    sort(A + 1, A+N+1);
    int64_t res = 1;  
    vector<int64_t> v;
    for(int i = 1; i < N; i++) 
    { 
        v.push_back((A[i + 1] - A[i] - 1) / X);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++)
    {
        if (v[i] <= 0)
        {
            continue;
        }
        if (K >= v[i])
        {
            K -= v[i];
        }
        else
        {
            res++;
        } 
    }
    cout << res << endl;
    return 0; 
}