Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(X) (X).begin(), (X).end()
- #define pb push_back
- #define rall(X) (X).rbegin(), (X).rend()
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define fir first
- #define sec second
- int main() {
- ll n; cin >> n;
- vector<ll> a(n);
- for (ll i = 0; i < n; i++) {
- cin >> a[i];
- }
- sort(rall(a));
- ll l = 0, r = n;
- while (r - l > 1) {
- ll tm = (l + r) / 2;
- vector<ll> b(tm, 1e9);
- bool ch = true;
- for (ll i = 0; i < n; i += tm) {
- for (ll j = i; j < min(i + tm, n); j++) {
- if (b[j - i] == 0) {
- ch = false;
- break;
- }
- b[j - i] = min(b[j - i] - 1, a[j]);
- }
- }
- if (ch == true) {
- r = tm;
- } else {
- l = tm;
- }
- }
- if (l == 0) {
- cout << r << '\n';
- return 0;
- }
- vector<ll> b(l, (ll)1e9);
- bool ch = true;
- for (ll i = 0; i < n; i += l) {
- for (ll j = i; j < min(i + l, n); j++) {
- if (b[j - i] == 0) {
- ch = false;
- break;
- }
- b[j - i] = min(b[j - i] - 1, a[j]);
- }
- }
- if (ch == true) {
- cout << l;
- } else {
- cout << r;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement