Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(X) (X).begin(), (X).end()
  6. #define pb push_back
  7. #define rall(X) (X).rbegin(), (X).rend()
  8. #define ll long long
  9. #define ull unsigned long long
  10. #define ld long double
  11. #define fir first
  12. #define sec second
  13.  
  14. int main() {
  15. ll n; cin >> n;
  16. vector<ll> a(n);
  17. for (ll i = 0; i < n; i++) {
  18. cin >> a[i];
  19. }
  20. sort(rall(a));
  21.  
  22. ll l = 0, r = n;
  23. while (r - l > 1) {
  24. ll tm = (l + r) / 2;
  25. vector<ll> b(tm, 1e9);
  26. bool ch = true;
  27. for (ll i = 0; i < n; i += tm) {
  28. for (ll j = i; j < min(i + tm, n); j++) {
  29. if (b[j - i] == 0) {
  30. ch = false;
  31. break;
  32. }
  33. b[j - i] = min(b[j - i] - 1, a[j]);
  34. }
  35. }
  36. if (ch == true) {
  37. r = tm;
  38. } else {
  39. l = tm;
  40. }
  41. }
  42.  
  43. if (l == 0) {
  44. cout << r << '\n';
  45. return 0;
  46. }
  47. vector<ll> b(l, (ll)1e9);
  48. bool ch = true;
  49. for (ll i = 0; i < n; i += l) {
  50. for (ll j = i; j < min(i + l, n); j++) {
  51. if (b[j - i] == 0) {
  52. ch = false;
  53. break;
  54. }
  55. b[j - i] = min(b[j - i] - 1, a[j]);
  56. }
  57. }
  58. if (ch == true) {
  59. cout << l;
  60. } else {
  61. cout << r;
  62. }
  63.  
  64. return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement