Advertisement
Mirbek

C. Очередь в банке

Jan 26th, 2022
771
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 30005;
  6.  
  7. int n;
  8. int t[N], s[N];
  9.  
  10. bool check(int k) {
  11.     multiset <int> ms;
  12.     for (int i = 0; i < k; i++) {
  13.         ms.insert(0);
  14.     }
  15.     for (int i = 1; i <= n; i++) {
  16.         if (*ms.begin() <= t[i] + 10) {
  17.             int new_t = max(*ms.begin(), t[i]) + s[i];
  18.             ms.erase(ms.begin());
  19.             ms.insert(new_t);
  20.         } else {
  21.             return false;
  22.         }
  23.     }
  24.  
  25.     return true;
  26. }
  27.  
  28. int main(){
  29.     cin >> n;
  30.  
  31.     for (int i = 1; i <= n; i++) {
  32.         cin >> t[i] >> s[i];
  33.     }
  34.  
  35.     int l = 1, r = n;
  36.  
  37.     while (l <= r) {
  38.         int md = (l + r) / 2;
  39.         if (check(md) == true) {
  40.             r = md - 1;
  41.         } else {
  42.             l = md + 1;
  43.         }
  44.     }
  45.  
  46.     cout << r + 1 << endl;
  47. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement