解题思路
首先将外卖按时间排序,然后模拟按时间依次取出外卖。在这里记录两个变量a和pre,pre表示上一外卖时间,a表示上一外卖的优先级。然后根据此次的外卖时间来更新pre和a。
在这里维护一个集合s,用于存放>5的外卖,动态进行维护,最后再根据最后求解的时间t来对s进行修改。
最后集合s的大小就是结果。
(模拟) $O(m)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<string>
#define ll long long
#define mod 1000000007
using namespace std;
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
const int maxn=1e5+5;
int n,m,t;
pair<int,int> q[maxn];
int main(){
cin>>n>>m>>t;
for(int i=0;i<m;i++){
int ts,id;
cin>>ts>>id;
q[i]={ts,id};
}
sort(q,q+m);
int cnt=0;
int pre[maxn]={0};
int a[maxn]={0};
set<int> s;
for(int i=0;i<m;i++){
int ts=q[i].first, id=q[i].second;
if(ts>t) break;
if(!pre[id]||pre[id]==ts) a[id]+=2;
else{
int d=ts-pre[id]-1;
a[id]=max(0, a[id]-d);
if(a[id]<=3) s.erase(id);
a[id]+=2;
}
if(a[id]>5) s.insert(id);
pre[id]=ts;
}
for(int i=1;i<=n;i++){
a[i]-=t-pre[i];
if(a[i]<=3&&s.count(i)) s.erase(i);
}
cout<<s.size();
return 0;
}
大佬,第二个for循环没看懂,可以再解释一下么?
第二个循环是根据时刻从小到大遍历所有外卖,记录他们的变化。
首先取出第i个外卖,如果当前外卖时间大于t,则表明所有小于t的外卖都取出,结束。
若第i个外卖之前没有出现过,或者说在这一时刻已经出现过,则直接将该外卖等级+2;
否则,查看第i个外卖的上一个到达时间,然后更新当前优先级,即从上一个时刻到这一时刻的时间差,若优先级降低后的时间<=3,则表明该外卖不在优先缓存中,剔除该外卖。最后再将第i个外卖的优先级+2。
每次遍历都要查看当前第i个外卖的优先级是否大于5,若是,则加入优先缓冲中。
注意一下pre数组是存第i个外卖的上一时刻,a数组是第i个外卖的上一时刻的优先级就好。
哇!太感谢了,讲的很清楚,打了这么多字太辛苦了
没事哈,有帮到就好啦