allia

очередь

Nov 25th, 2020 (edited)
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6. class IQueue
  7. {
  8.    int *arr, length, first, last;
  9. public:
  10.    IQueue(int len);
  11.    void push(int val);
  12.    int pop();
  13. };
  14.  
  15. IQueue::IQueue(int len)
  16. {
  17.    arr = new int [len];
  18.    length = len;
  19.    first = 0;
  20.    last = -1;
  21. }
  22.  
  23. void IQueue::push(int val)
  24. {
  25.    if (last < length-1)
  26.       arr[++last] = val;
  27. }
  28.  
  29. int IQueue::pop()
  30. {
  31.    if (first == last+1)
  32.      return -1;
  33.    return arr[first++];
  34. }
  35.  
  36.  void sift_all (int *arr, int first, int last)
  37.  
  38.  {
  39.   int j = first;
  40.   int k = first*2+1;
  41.  
  42.   while (k <= last)
  43.   {
  44.     if (k < last && arr[k+1] < arr[k])
  45.      k++;
  46.      if (arr[j] < arr[k])
  47.      break;
  48.      else if (arr[j] >= arr[k])
  49.      {
  50.         swap(arr[j], arr[k]);
  51.          j = k;
  52.          k = k*2+1;
  53.      }
  54.  }
  55. }
  56.  
  57. int main()
  58. {
  59.   int n, k, time_i;
  60.   cin >> n >> k;
  61.  
  62.   IQueue train_ticket(n);
  63.  
  64.   for (int i = 0; i < n; i++)
  65.    {
  66.      cin >> time_i;
  67.      train_ticket.push(time_i);
  68.    }
  69.  
  70.   int *kassa = new int[k];
  71.  
  72.   for (int i = 0; i < k; i++)
  73.    kassa[i] = 0;
  74.  
  75.   for (int i = 0; i < n; i++)
  76.   {
  77.     time_i = train_ticket.pop();
  78.     sift_all(kassa, 0, k-1);
  79.     kassa[0] += time_i;
  80.   }
  81.  
  82.   int max = 0;
  83.  
  84.   for (int i = 1; i < k; i++)
  85.    if (kassa[i] > kassa[max])
  86.     max = i;
  87.  
  88.   cout << kassa[max];
  89. }
RAW Paste Data