题目描述

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

暴力:
枚举每个时刻，每个店里的有订单个数，和没有订单的店，(1e5*1e5)必定超时，

优化：

把一段连续的没有购买订单的这一段统一放到下一次购买的时间来处理，只需要考虑有订单的店，

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,T;
int cnt;
typedef pair<int,int> PII;
PII order[100005];
int st[100005];//代表店号i是否加入了优先缓存
int score[100005];
int last[100005];//代表店号i上一次有订单的时刻   
int main(int argc, char** argv) {
    scanf("%d%d%d",&n,&m,&T);
    for(int i=0;i<m;i++){
        scanf("%d%d",&order[i].first,&order[i].second);
    //first表示时刻，second表示订单店号
    }
    sort(order,order+m);//对pair进行排序，按第一个参数从小到大，第一个参数相等时，再按第二个参数从小到大排序
    for(int i=0;i<m;){
        int j=i;
        while(j<m&&order[i]==order[j]){//相同订单的个数，时刻和订单店号均相同
            j++;    
    }
    int t=order[i].first,id=order[i].second;
    cnt=j-i;//相同订单的个数
    i=j;
    score[id]-=(t-last[id]-1);//一段连续的没有购买订单的这一段统一放到下一次购买的时间来处理
    if(score[id]<0)  score[id]=0;
    if(score[id]<=3) st[id]=0;
    score[id]+=2*cnt;
    if(score[id]>5) st[id]=1;
    last[id]=t;
    }
    for(int i=1;i<=n;i++){
        if(last[i]<T){   //若T时刻该店没有订单，则要减去其上次店号i有订单时间到T的时间距离。
           score[i]-=(T-last[i]);
        }
        if(score[i]<=3) st[i]=0;
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res+=st[i];      //加入优先缓存的st[]是1,没有加入优先缓存的st[]是0 
    }
    printf("%d\n",res); 
    return 0;
}