[蓝桥杯][2019年第十届真题]外卖店优先级

题目链接

“饱了么”外卖系统中维护着 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≤10^5,
1≤ts≤T,
1≤id≤N
输入样例：
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例：
1
样例解释
6时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。所以是有 1
家店 (2 号) 在优先缓存中。

#include<bits/stdc++.h>
using namespace std;
int n,m,T;
struct Time{
    
	int t;//时刻 
	int id;//外卖店编号 
}ti[100005];
struct Shop{
    
	int pre;//上一个收到订单的时刻 
	int prior;//当前店的优先级 
	bool flag;//当前店是否在优先缓存？是：true 否：false 
}s[100005];
bool cmp(Time x,Time y){
    
	if(x.t!=y.t){
    
		return x.t<y.t;
	}else return x.id<y.id;
}
int cnt;
int main(){
    
	cin>>n>>m>>T;
	for(int i=0;i<m;i++){
    
		cin>>ti[i].t>>ti[i].id;
	} 
	sort(ti,ti+m,cmp);
	for(int i=0;i<m;i++){
    
		if(ti[i].t>=T+1){
    
			break;
		}
		//因为一个时刻一个外卖店可能收到多份订单，所以需要判断一下
		if(s[ti[i].id].pre!=ti[i].t) s[ti[i].id].prior-=(ti[i].t-s[ti[i].id].pre-1);
		if(s[ti[i].id].prior<0) s[ti[i].id].prior=0;
		if(s[ti[i].id].prior<=3&&s[ti[i].id].flag){
    
			s[ti[i].id].flag=false;
		}
		s[ti[i].id].prior+=2;
		if(s[ti[i].id].prior>5&&!s[ti[i].id].flag){
    
			s[ti[i].id].flag=true;
		}
		
		s[ti[i].id].pre=ti[i].t;
	}
	for(int i=1;i<=n;i++){
    
		if(s[i].flag){
    
			int temp=s[i].prior-(T-s[i].pre);
			if(temp<=3) s[i].flag=false;
		}
	}
	for(int i=1;i<=n;i++){
    
		cnt+=s[i].flag;
	}
	cout<<cnt<<endl;
	return 0;
}