AcWing 1241. 外卖店优先级
原题链接
简单
作者:
重柔道人
,
2021-04-06 17:29:27
,
所有人可见
,
阅读 384
解释y总de代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
int f[N];//表示店铺的优先级
int st[N];//判断店铺是否在有优先缓存中
int last[N];//last[i] 表示店铺i上一次有订单的时刻
PII order[N];//订单
//同一批订单表示时刻和id都相同的外卖,
//由于进行了排序,所以同一时刻的所有订单是连续排列的
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].first,&order[i].second);
}
sort(order,order+m);
for(int i=0;i<m;)
{
int j=i;
while(order[i]==order[j] && j<m) j++;//循环寻找同一批订单最后一个的位置
int t=order[i].first,id=order[i].second,cnt=j-i;//cnt表示同一批订单的外卖数量
i=j;
f[id]-=t-last[id]-1;//时刻5 -- 时刻 7 中间只有一个数6 7-5-1=1
if(f[id]<0) f[id]=0;
if(f[id]<=3) st[id]=0;//把t时刻之前的处理完,然后就可以算t时刻的订单了
f[id] +=cnt*2;
if(f[id]>5) st[id]=1;
last[id]=t;//下个时刻减去这个时刻再减1就是优先级该减去的数目
}
for(int i=1;i<=n;i++)
{
if(last[i]<T)
{
f[i]-=T-last[i];
if(f[i]<=3) st[i]=0;
}
}
int ans=0;
for(int i=1;i<=n;i++) ans+=st[i];
cout <<ans << endl;
return 0;
}