Codeforces Round #727 (Div. 2)C. Stable Groups
给一个数组, 求加入n个数字(大小不限)后, 使得数组中两个的差不大于k. 求n是多少.
这题贪心, 就是每次都取加入最大的数字.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#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; } |