第十届蓝桥杯大赛软件类省赛 C/C++ 大学 A 组试题 G: 外卖店优先级 20

（题外话

此题的方法是一个大佬教我的，我写这篇文章其一是想再巩固一下，另外能给其他小伙伴一些启发就更棒啦

“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。

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

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

输出一个整数代表答案。

样例解释
6 时刻时， 1 号店优先级降到 3，被移除出优先缓存； 2 号店优先级升到 6，
加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
评测用例规模与约定
对于 80% 的评测用例， 1 ≤ N; M; T ≤ 10000。
对于所有评测用例， 1 ≤ N; M; T ≤ 100000， 1 ≤ ts ≤ T， 1 ≤ id ≤ N。

Input

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

Output

1

先创建一个数组，依次存下所有时间和外卖店，使用sort数组将时间顺序从小到大排列，再建立一个bool类型数组判断是否达到优先缓存的要求，若达到便将此外卖店存入ans数组中。建立两个数组last[] 和key[]，一个存放最后接到订单的时间，另一个判断优先级，所有数组初始都为0。

先用for循环遍历每一个订单，判断此订单时间与last数组中的最后接单时间是否一致，不一致则用当前优先级减去这个时间差。还需要判断优先级是否小于0、在此时间段这个外卖店是否需要从优先缓存中移除等，然后更新优先级和最后接单时间。每个订单遍历完之后查看每个店的最后接到订单的时间与T时刻时间是否一致，不一致则每一秒需要减去1个优先级，更新ans数组，将优先级降到3及以下的外卖店从ans数组中移除，最后遍历一遍ans数组即可。

#include 
#include 
using namespace std;
const int N = 1e5+10;
struct Node{
	int ts,id;
}a[N];
int n,m,t;
int last[N];//每一个店最后接到订单的时间 
int key[N];//判断优先级是否小于0 
bool ans[N];//判断是否在优先缓存里 

int cmp(Node x,Node y){//时间顺序从小到大排列 
	if(x.ts != y.ts )	return x.ts < y.ts ;
	else	return x.id < y.id ;
}
int main(){
	cin>>n>>m>>t;
	for(int i = 1; i <= m; i++)
		cin>>a[i].ts >>a[i].id ;
	sort(a+1,a+m+1,cmp);
	for(int i = 1; i <= m; i++){//遍历每一个订单 
		if(a[i].ts != last[a[i].id])//判断每个订单的时间于last数组时间是否相同 
			key[a[i].id] -= a[i].ts - last[a[i].id] - 1;//不同则要用优先级减去差值 
		if(key[a[i].id] < 0)//如果优先级小于0，则让它为0 
			key[a[i].id] = 0;
		if(key[a[i].id] <= 3)
			ans[a[i].id] = false;//如果ans[]降到了3或3以下，就从优先缓存中移除
		key[a[i].id] += 2;//收到的每个订单都需要+2 
		last[a[i].id] = a[i].ts ;//更新最后时间 
		if(key[a[i].id] > 5) //优先级大于5，则进入优先缓存 
			ans[a[i].id] = true;
	}
	for(int i = 1; i <= n; i++){//在t时刻每个店的优先级 
		if(last[i] < t)
			key[i] -= t - last[i];
		if(key[i] <= 3)
			ans[i] = false; 
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++)//遍历ans数组，记录此时有多少店在优先缓存中 
		if(ans[i])	cnt++;
	cout<