算法思想

1.每家店铺维护一个订单清单，该清单记录所有订单的时刻与该时刻的订单数，每张订单表都用 map 来维护。
2.遍历所有的订单表。对于每一张订单表，按时间顺序遍历所有订单，记录最终该店铺是否在缓存中。
3.统计在缓存中的店铺的数量，即为所求的答案。

Algorithm 1:

Time Complexity = $O(n + m)$ , the Worst Time Complexity = $O(n + m \log m)$ .

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int shopsInCache(vector<map<int, int>>& shops, int t) {
    int res = 0;
    for (auto shop : shops) {
        bool inCache = false;
        int priority = 0;
        int preTs = 0;
        for (auto [curTs, cnt] : shop) {
            // No orders during [preTs, curTs - 1]
            priority = max(0, priority - (curTs - 1 - preTs));
            if (priority <= 3) {
                inCache = false;
            }

            priority += cnt * 2;
            if (priority > 5) {
                inCache = true;
            }

            preTs = curTs;
        }

        // No orders during [preTs, t]
        priority = max(0, priority - (t - preTs));
        if (priority <= 3) {
            inCache = false;
        }
        res += inCache;
    }

    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, t;
    cin >> n >> m >> t;

    // map<ts, ts_count>
    vector<map<int, int>> shops(n);
    while (m--) {
        int ts, id;
        cin >> ts >> id;
        shops[id - 1][ts]++;
    }

    cout << shopsInCache(shops, t) << '\n';

    return 0;
}

Algorithm 2：

Time Complexity = $O(n + m)$ , the Worst Time Complexity = $O(n + m \log m)$ .

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int shopsInCache(vector<vector<int>>& shops, int t) {
    int res = 0;
    for (auto& shop : shops) {
        sort(shop.begin(), shop.end());

        bool inCache = false;
        int score = 0, preTs = 0;
        int m = shop.size();
        for (int i = 0; i < m; i++) {
            int curTs = shop[i];
            int cnt = 1;      // Number of orders at the current time
            int j = i + 1;
            while (j < m && shop[j] == curTs) {
                cnt++;
                j++;
            }
            i = j - 1;

            // No orders during [preTs, curTs - 1]
            score = max(0, score - (curTs - 1 - preTs));
            if (score <= 3) {
                inCache = false;
            } 

            score += cnt * 2;
            if (score > 5) {
                inCache = true;
            }

            preTs = curTs;
        }

        // No orders during [preTs, t]
        score = max(0, score - (t - preTs));
        if (score <= 3) {
            inCache = false;
        }
        res += inCache;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, t;
    cin >> n >> m >> t;

    vector<vector<int>> shops(n);
    while (m--) {
        int ts, id;
        cin >> ts >> id;
        shops[id - 1].push_back(ts);
    }

    cout << shopsInCache(shops, t) << '\n';

    return 0;
}