Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_DISABLE_PERFCRIT_LOCKS
- #include <iomanip>
- #include <iostream>
- #include <vector> // Лишние инклюды для маленькой программы не критичны, но в больших проектах,
- #include <utility> // где compile-time может достигать 30 минут, лучше их не оставлять.
- #include <map>
- // Простой пример, когда using namespace std негативно повлияет на программу: https://godbolt.org/z/e8zf1azx9
- // Clang компилирует этот код, а MSVC - нет (т.к. в iostream подключается функция std::count из algorithm)
- //
- // Если не охота писать std, то вместо using namespace лучше явно перечислить что будет использоваться:
- // using std::map;
- // using std::cin;
- // using std::cout;
- using namespace std;
- class ReadingManager {
- public:
- // Во многих кодстайлах рекомендуется использовать const везде, где можно.
- // Это сократит шанс возникновения ошибок (при попытке изменить то, что изначально не предполагалось изменить).
- // И позволяет быстрее читать код - в голове будет информация о том, что переменная не меняется.
- void Read(int user_id, int page_count) {
- // Чтобы два раза не искать user_id в pages_by_users
- // можно один раз получить итератор
- if (pages_by_users.count(user_id)) {
- auto old_count = pages_by_users[user_id];
- users_by_pages[old_count]--;
- }
- pages_by_users[user_id] = page_count;
- users_by_pages[page_count]++;
- }
- double Cheer(int user_id) const {
- if (!pages_by_users.count(user_id)) {
- return 0;
- }
- if (pages_by_users.size() == 1) {
- return 1;
- }
- auto read_by_user = pages_by_users.at(user_id);
- int total_users_less = 0;
- for (auto it : users_by_pages) {
- if (it.first >= read_by_user) {
- break;
- }
- total_users_less += it.second;
- }
- return double(total_users_less) / (pages_by_users.size() - 1);
- }
- private:
- // У std::map удаление/поиск/вставка работают за О(log(n))
- //
- // Обычно этот контейнер реализуется с помощью красно черного дерева.
- // И чем больше данных будет храниться, тем больше узлов нужно пройти, чтобы найти нужную вершину.
- //
- // В нашем случае лучше использовать std::unordered_map, т.к. удаление/поиск/вставка будут работать за О(1)
- map<int, int> pages_by_users;
- // Так как количество страниц заранее известно и не сильно большое, то можно попробовать заменить на std::array<int, 1000>.
- // Каждый элемент массива показывает, сколько человек находятся на этой странице.
- //
- // Мы потратим sizeof(int) * 1000 байт, но получим кэш-френдли структуру со сложностью О(1)
- // И хоть у std::unordered_map сложность аналогичная, но в отличие от std::array есть затраты на
- // вычисление хеша ключа + реалокацию.
- map<int, int> users_by_pages;
- };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- ReadingManager manager;
- int query_count;
- cin >> query_count;
- int query_id = 0;
- // Может быть стоит заменить while на for, чтобы инициализация и сравнение было в одном месте.
- // for (int query_id = 0; query_id < query_count; query_id++) {
- while (query_id < query_count) {
- string query_type;
- cin >> query_type;
- int user_id;
- cin >> user_id;
- if (query_type == "READ") {
- int page_count;
- cin >> page_count;
- manager.Read(user_id, page_count); // Read -> HandleRead
- }
- else if (query_type == "CHEER") {
- cout << setprecision(6) << manager.Cheer(user_id) << "\n";
- }
- ++query_id;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment