原题链接：外卖店的优先级

题目描述

“饱了么”外卖系统中维护着 $N$ 家外卖店，编号 $1∼N$。

每家外卖店都有一个优先级，初始时 ($0$ 时刻) 优先级都为 $0$。

每经过 $1$ 个时间单位，如果外卖店没有订单，则优先级会减少 $1$，最低减到 $0$；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 $2$。

如果某家外卖店某时刻优先级大于 $5$，则会被系统加入优先缓存中；如果优先级小于等于 $3$，则会被清除出优先缓存。

给定 $T$ 时刻以内的 $M$ 条订单信息，请你计算 $T$ 时刻时有多少外卖店在优先缓存中。

输入格式

第一行包含 $3$ 个整数 $N,M,T。$

以下 $M$ 行每行包含两个整数 $ts$ 和 $id$，表示 $ts$ 时刻编号 $id$ 的外卖店收到一个订单。

输出格式

输出一个整数代表答案。

数据范围

$1≤N,M,T≤105,$
$1≤ts≤T,$
$1≤id≤N$

输入样例1：

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出样例1：

1

思路

我自己做的时候本来是想着排序，然后枚举每个订单在这个时刻的状态，再做操作，但这样的时间复杂度就是$O(n^2)$，明显会超时

那么优化我们可以将没有订单的一段时间一次处理，我们只需要存每个店铺上一次有订单的时间，那么处理时就只在有订单的时候，减去和上一次有订单时间的偏移量就是无订单时候减去的优先级。这样我们就可以减少一层遍历

而且对于同一时间点同一店铺来的订单，我们可以批量处理

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;

const int N = 100010;

bool st[N];     // 优先缓存
int prit[N];    // 店铺的优先级
int last[N];    // 上一次有订单的时间
PII order[N];   // 订单列表 
int n, m, T;

int main()
{
    cin >> n >> m >> T;
    for(int i = 0;i < m;i ++) scanf("%d%d",&order[i].x,&order[i].y);
    sort(order,order + m);

    for(int i = 0;i < m;) {

        int j = i;
        while(j < m && order[j] == order[i]) j ++;
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;

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

        prit[id] += cnt * 2;
        if(prit[id] > 5) st[id] = true;

        last[id] = t;
    }

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

    int res = 0;
    for(int i = 1;i <= n;i ++) 
        if(st[i]) res ++;

    cout << res << endl;
    return 0;
}