题目描述
“饱了么”外卖系统中维护着 N家外卖店,编号 1∼N
每家外卖店都有一个优先级,初始时 (0时刻) 优先级都为 0
每经过 1个时间单位,如果外卖店没有订单,则优先级会减少1,最低减到0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2
如果某家外卖店某时刻优先级大于5,则会被系统加入优先缓存中;如果优先级小于等于 3,则会被清除出优先缓存。
给定 T时刻以内的 M条订单信息,请你计算 T时刻时有多少外卖店在优先缓存中。
样例
输入样例:
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例:
1
算法
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int score[N],last[N]; //score表示第i个店的当前优先级,last表示第i个店上次有订单的时间
bool st[N]; //表示第i个店是否在优先级当中
PII order[N]; //用pair来存每条信息
int main(){
int n,m,T;
scanf("%d%d%d",&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[i]==order[j]) j++; //用j记录相同订单的长度(数量)
int t=order[i].x,id=order[i].y,cnt=j-i; //记录在t时间,id号店铺,有cnt个订单
i=j; //j为下一个order订单不同的位置,把i的位置换成从j开始
score[id]-=t-last[id]-1; //减去优先级
if(score[id]<0) score[id]=0; //判断是否加入优先级
if(score[id]<=3) st[id]=false;
score[id]+=cnt*2;
if(score[id]>5) st[id]=true;
last[id]=t;
}
for(int i=1;i<=n;i++){ //判断到T是否还有未减去的优先级
if(last[i]<T) score[i]-=T-last[i];
if(score[i]<=3) st[i]=false;
}
int res=0; //判断每家店铺的true和false数量
for(int i=1;i<=n;i++)
res+=st[i];
printf("%d",res);
return 0;
}