分析

这题我们的关键是某家外卖店某时刻优先级大于5，则会被系统加入优先缓存中；如果优先级小于等于3，则会被清除出优先缓存。由于订单数量、店铺数量和时间达到$10^5$，我们不能通过时间来枚举每一份订单，这样必然会超时。那么我们该怎么做呢？我们这样想，对于一家店铺来说，在一条时间轴上，必然是有一些时间点有订单，有些点没有订单。那么我们可以枚举每一批次订单，这些订单是同一时刻同一店铺的，这样的话时间复杂度就降到$O(m)$。

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n, m, T;
int f[100010];//  f[i]表示店铺i的优先级
int st[100010];//  st[i]表示店铺i是否处于优先缓存
int last[100010];//  last[i]表示店铺i上一次有订单的时间 
PII order[100010];//  订单 
int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &order[i].first, &order[i].second);
    } 
    sort(order, order + m);
    for (int i = 0; i < m;)
    {
        int j = i;
        while (order[i] == order[j] && j < m) j++;
        int t = order[i].first, id = order[i].second, cnt = j - i;
        i = j;

        f[id] -= t - last[id] - 1;
        if (f[id] < 0) f[id] = 0;
        if (f[id] <= 3) st[id] = 0;

        f[id] += cnt * 2;
        if (f[id] > 5) st[id] = 1;

        last[id] = t;
    }

    for (int i = 1; i <= n; i++)
    {
        if (last[i] < T)
        {
            f[i] -= T - last[i];
            if (f[i] <= 3) st[i] = 0;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans += st[i];
    cout << ans << endl;
    return 0;
}