题目描述

“饱了么”外卖系统中维护着 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

输入样例

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

输出样例

1

C++ 代码

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


const int _max =1e5+1;
int n, m, T;
vector<int> orders[_max];
int main()
{

    cin>>n>>m>>T;
    for(int i=1,x,y;i<=m;++i)
    {
        cin>>x>>y;
        orders[y].push_back(x);
    }
    int priority=0;//鉴于 优先级只是一个判断店家是否在队列的中间变量，所以我们不需要一个数组把每家店的优先级存储起来。
    int is_in_queue[n+1];
    int count=0;//记录有多少个在队列 

    ///计算T时刻在队列 的店有多少家(count) 
    for(int i=1;i<=n;++i)
    {
        if(orders[i].size()==0) continue;
        sort(orders[i].begin(),orders[i].end());//排序i号店的订单 
        priority=0;//重置 
        //对于i号店，计算当它收到最后一个订单时，优先级是多少
        for(int j=0;j<orders[i].size();++j)//j遍历i号店的订单
        //情况一:由于优先级最低是0,所以无论时刻是多少,遇到第一个订单前是总是0,遍历到第一个订单直接把优先级+2
        //情况二:多个订单(j>0)在同一时刻来,【优先级】+= 同一时刻订单数量*2 或 if(当前j遍历订单与上一个订单是同一时刻)  【优先级】 再加2; 
        //情况三:当前订单与上一个订单的时刻不同,则先减去 一定的优先级(根据经过订单间时间差算,注意不要把当前时刻也算进去了,优先级最低为0) ， 然后【优先级】 加2;
        {

            if(j>0&&orders[i][j]!=orders[i][j-1]) //注意j>0时进入这个if,避免 a[i][j-1]访问到 a[i][-1]
            {
                priority-=(orders[i][j]-orders[i][j-1]-1);
                if(priority<0) priority=0;
                if(priority<=3) is_in_queue[i]=false;//这里记得实时更新 i店是否在队列 
            }
            //鉴于上面三种情况都会把 优先级+2 ,所以这个操作可以提取出来
            //注： 优先级+2在第二种情况中是最后的操作， 所以提取出来的时候不能放在if块前面 
            priority+=2;
            //每次计算完优先级都需要更新 i店是否在队列 
            if(priority>5) is_in_queue[i]=true;
        }

        //查询T时刻是否有在队列，根据题意【最后订单时刻】<=T，即要根据经过的时间一定要减去优先级 

        if(orders[i].size()) priority-=(T-orders[i][ orders[i].size()-1 ]);
        //刚把权重减完所以需要检测 
        if(priority<=3) is_in_queue[i]=false;
        if(is_in_queue[i]) ++count;
    }
    cout<<count<<endl;

    return 0;
}