AcWing 1241. 外卖店优先级
原题链接
简单
作者:
茶_8
,
2022-02-25 19:43:14
,
所有人可见
,
阅读 168
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n,m,t;
int a[N]={0};
bool success[N];
//核心:如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果优先级小于等于 3,则会被清除出优先缓存。
//success数组,记录当前优先级小于5的数组,看是否还在缓冲队列中
//让每家店铺按id为第一关键字,时间为第二关键字排序
struct Time
{
int idx,t;
bool operator<(const Time &T)
{
if(T.idx!=idx) return idx<T.idx;
return t<T.t;
}
}times[N];
int main()
{
cin>>n>>m>>t;
for(int i =0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
times[i]={b,a};
}
sort(times,times+m);
int st=1,ed=1,id=1;
//双指针扫描每一个数据,st为下一个有订单的时间点,ed为本次有外卖的时间点,id记录为当前店铺的编号
for(int i =0;i<m;i++)
{
auto e = times[i];
//不是前一个外卖店,则需计算
if(id!=e.idx)
{
cout<<st<<endl;
int s = a[id];
if(st<t) a[id]+=st-t;
if(s>5 && a[id]>3) success[id]=true;
st=ed=1;
}
st=e.t;
if(st==ed || st==ed+1)
{
a[e.idx]+=2;
ed=st;
}
else
{
a[e.idx]+=ed-st+1;
if(a[e.idx]<0) a[e.idx]=0;
ed=st;
a[e.idx]+=2;
}
id=e.idx;
}
//扫尾
int s=a[id];
if(st<t) a[id]+=st-t;
if(s>5 && a[id]>3) success[id]=true;
int res=0;
for(int i =1;i<=n;i++)
{
if(a[i]>5 || success[i]) res++;
}
cout<<res<<endl;
return 0;
}