API tools faq
paste
Advertisement
kutuzzzov

Урок 9 Амортизированная сложность

kutuzzzov
Nov 9th, 2022
1,519
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
raw download clone embed print report
  1. #include <algorithm>
  2. #include <deque>
  3. #include <string>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. struct Ticket {
  9.     int id;
  10.     string name;
  11. };
  12.  
  13. class TicketOffice {
  14. public:
  15.     // добавить билет в систему
  16.     void PushTicket(const string& name) {
  17.         Ticket toAdd;
  18.         toAdd.id = last_id_;
  19.         toAdd.name = name;
  20.         ++last_id_;
  21.         tickets_.push_back(toAdd);
  22.     }
  23.  
  24.     // получить количество доступных билетов
  25.     int GetAvailable() const {
  26.         return tickets_.size();
  27.     }
  28.  
  29.     // получить количество доступных билетов определённого типа
  30.     int GetAvailable(const string& name) const {
  31.         return count_if(tickets_.begin(), tickets_.end(), [name](Ticket ticket)
  32.             {
  33.                 return ticket.name == name;
  34.             });
  35.     }
  36.  
  37.     // отозвать старые билеты (до определённого id)
  38.     void Invalidate(int minimum) {
  39.         while (!tickets_.empty() && tickets_.front().id < minimum) {
  40.                 tickets_.pop_front();
  41.         }
  42.     }
  43.  
  44. private:
  45.     int last_id_ = 0;
  46.     deque<Ticket> tickets_;
  47. };
  48.  
  49. int main()
  50. {
  51.     TicketOffice tickets;
  52.  
  53.     tickets.PushTicket("Swan Lake"); // id - 0
  54.     tickets.PushTicket("Swan Lake"); // id - 1
  55.     tickets.PushTicket("Boris Godunov"); // id - 2
  56.     tickets.PushTicket("Boris Godunov"); // id - 3
  57.     tickets.PushTicket("Swan Lake"); // id - 4
  58.     tickets.PushTicket("Boris Godunov"); // id - 5
  59.     tickets.PushTicket("Boris Godunov"); // id - 6
  60.  
  61.     cout << tickets.GetAvailable() << endl; // Вывод: 7
  62.     cout << tickets.GetAvailable("Swan Lake") << endl; // Вывод: 3
  63.     cout << tickets.GetAvailable("Boris Godunov") << endl; // Вывод: 4
  64.  
  65.     // Invalidate удалит билеты с номерами 0, 1, 2:
  66.     tickets.Invalidate(3);
  67.  
  68.     cout << tickets.GetAvailable() << endl; // Вывод: 4
  69.     cout << tickets.GetAvailable("Swan Lake") << endl; // Вывод: 1
  70.     cout << tickets.GetAvailable("Boris Godunov") << endl; // Вывод: 3
  71.  
  72.     tickets.PushTicket("Swan Lake"); // id - 7
  73.     tickets.PushTicket("Swan Lake"); // id - 8
  74.  
  75.     cout << tickets.GetAvailable("Swan Lake") << endl; // Вывод: 3
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!