Gistrec

Code Review

Nov 7th, 2021 (edited)
1,274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.74 KB | None | 0 0
  1. #define _CRT_DISABLE_PERFCRIT_LOCKS
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <vector>  // Лишние инклюды для маленькой программы не критичны, но в больших проектах,
  5. #include <utility> // где compile-time может достигать 30 минут, лучше их не оставлять.
  6. #include <map>
  7.  
  8. // Простой пример, когда using namespace std негативно повлияет на программу: https://godbolt.org/z/e8zf1azx9
  9. // Clang компилирует этот код, а MSVC - нет (т.к. в iostream подключается функция std::count из algorithm)
  10. //
  11. // Если не охота писать std, то вместо using namespace лучше явно перечислить что будет использоваться:
  12. // using std::map;
  13. // using std::cin;
  14. // using std::cout;
  15. using namespace std;
  16.  
  17. class ReadingManager {
  18. public:
  19.     // Во многих кодстайлах рекомендуется использовать const везде, где можно.
  20.     // Это сократит шанс возникновения ошибок (при попытке изменить то, что изначально не предполагалось изменить).
  21.     // И позволяет быстрее читать код - в голове будет информация о том, что переменная не меняется.
  22.     void Read(int user_id, int page_count) {
  23.         // Чтобы два раза не искать user_id в  pages_by_users
  24.         // можно один раз получить итератор
  25.         if (pages_by_users.count(user_id)) {
  26.             auto old_count = pages_by_users[user_id];
  27.             users_by_pages[old_count]--;
  28.         }
  29.         pages_by_users[user_id] = page_count;
  30.         users_by_pages[page_count]++;
  31.     }
  32.  
  33.     double Cheer(int user_id) const {
  34.         if (!pages_by_users.count(user_id)) {
  35.             return 0;
  36.         }
  37.         if (pages_by_users.size() == 1) {
  38.             return 1;
  39.         }
  40.  
  41.         auto read_by_user = pages_by_users.at(user_id);
  42.         int total_users_less = 0;
  43.         for (auto it : users_by_pages) {
  44.             if (it.first >= read_by_user) {
  45.                 break;
  46.             }
  47.             total_users_less += it.second;
  48.         }
  49.  
  50.         return double(total_users_less) / (pages_by_users.size() - 1);
  51.     }
  52.  
  53. private:
  54.     // У std::map удаление/поиск/вставка работают за О(log(n))
  55.     //
  56.     // Обычно этот контейнер реализуется с помощью красно черного дерева.
  57.     // И чем больше данных будет храниться, тем больше узлов нужно пройти, чтобы найти нужную вершину.
  58.     //
  59.     // В нашем случае лучше использовать std::unordered_map, т.к. удаление/поиск/вставка будут работать за О(1)
  60.     map<int, int> pages_by_users;
  61.  
  62.     // Так как количество страниц заранее известно и не сильно большое, то можно попробовать заменить на std::array<int, 1000>.
  63.     // Каждый элемент массива показывает, сколько человек находятся на этой странице.
  64.     //
  65.     // Мы потратим sizeof(int) * 1000 байт, но получим кэш-френдли структуру со сложностью О(1)
  66.     // И хоть у std::unordered_map сложность аналогичная, но в отличие от std::array есть затраты на
  67.     // вычисление хеша ключа + реалокацию.
  68.     map<int, int> users_by_pages;
  69. };
  70. int main() {
  71.     ios::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.     ReadingManager manager;
  74.     int query_count;
  75.     cin >> query_count;
  76.     int query_id = 0;
  77.     // Может быть стоит заменить while на for, чтобы инициализация и сравнение было в одном месте.
  78.     // for (int query_id = 0; query_id < query_count; query_id++) {
  79.     while (query_id < query_count) {
  80.         string query_type;
  81.         cin >> query_type;
  82.         int user_id;
  83.         cin >> user_id;
  84.         if (query_type == "READ") {
  85.             int page_count;
  86.             cin >> page_count;
  87.             manager.Read(user_id, page_count); // Read -> HandleRead
  88.         }
  89.         else if (query_type == "CHEER") {
  90.             cout << setprecision(6) << manager.Cheer(user_id) << "\n";
  91.         }
  92.         ++query_id;
  93.     }
  94.     return 0;
  95. }
Add Comment
Please, Sign In to add comment