AcWing 1241. 外卖店优先级
原题链接
简单
作者:
Will_15
,
2023-02-07 10:31:58
,
所有人可见
,
阅读 155
//main:输入个数,行数,时间,输入数据,排序,遍历所有数据,减去没有,不能为0,不行出去,加上,行上来,
//处理最后时刻,遍历加加,输出
//在纸上写出自己的暴力做法然后再优化
//在比赛中实在想不出了,就直接写暴力,超时就超时,能过几个样例就过几个样例
//一段时间有一段时间没有,我们可以记录上一次的便于计算
#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=100010;
int cnt[N],last[N];
bool st[N];
int main()
{
int n,m,t;
cin>>n>>m>>t;
vector<PII>s;
while(m--)
{
int a,b;
cin>>a>>b;
s.push_back({a,b});
}
sort(s.begin(),s.end());//排序,vector<int>s,用s.end();
for(PII e:s)
{
int t=e.x,id=e.y;//两边都有所以要减1
if(t!=last[id])cnt[id]=cnt[id]-(t-last[id]-1);//可能同一时刻,就不需要再算了
last[id]=t;//得到上一次有订单的时候
if(cnt[id]<0)cnt[id]=0;//小于零要回到0//一段时间有一段时间没有,我们可以记录上一次的便于计算
if(cnt[id]<=3)st[id]=false;//减完之后小于等于3就出去了,只有再次大于5才可以进
//怎样的过程得到怎么的结果,这个顺序也不能忘
//应该严格按照题目整个过程一步一步的顺序模拟
cnt[id]+=2;
if(cnt[id]>5)st[id]=true;//大于5
}
for(int i=1;i<=n;i++)
{
if(last[i]<t)//最后处理t时刻没有订单的情况
{
cnt[i]=cnt[i]-(t-last[i]);//last[i]有订单,最后没有订单所以不用减1
if(cnt[i]<=3)st[i]=false;
}
}
int res=0;
for(int i=1;i<=n;i++)
{
if(st[i])res++;
}
cout<<res<<endl;
return 0;
}