思路
例子:id为1的店铺,排序后的ts:1,3,5,6,问t=6时刻优先级为多少
正常模拟过程:
ts=1,优先级为2(有一个订单,优先级+2)
ts=2,优先级为1(没有订单,优先级-1)
ts=3,优先级为3(有一个订单,优先级+2)
ts=4,优先级为2(没有订单,优先级-1)
ts=5,优先级为4(有一个订单,优先级+2)
ts=6,优先级为6(有一个订单,优先级+2)
代码过程:
d=1时
pre=0,if(d!=pre) c-=d-pre-1;(即新优先级=旧优先级-(d-pre-1)=0)
在d=1时有订单,优先级+2,此时优先级为2;
pre=d=1
d=3时
pre=1,if(d!=pre) c-=d-pre-1;(即新优先级=旧优先级-(d-pre-1)=1)
在d=3时有订单,优先级+2,此时优先级为3;
pre=d=3
d=5时
pre=3,if(d!=pre) c-=d-pre-1;(即新优先级=旧优先级-(d-pre-1)=2)
在d=5时有订单,优先级+2,此时优先级为4;
pre=d=5
d=6时
pre=5,if(d!=pre) c-=d-pre-1;(即新优先级=旧优先级-(d-pre-1)=4)
在d=5时有订单,优先级+2,此时优先级为6;
pre=d=6
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int n,m,t;
vector<int> dd[N];
int ans;
int main(){
cin>>n>>m>>t;
for(int i=1;i<=m;i++){
int ts,id;
cin>>ts>>id;
dd[id].push_back(ts);
}
for(int id=1;id<=n;id++){
sort(dd[id].begin(),dd[id].end());//对同一id的店铺,有订单的时间进行排序
int c=0,pre=0;
bool f=false;
/*
d表示当前有订单的时间,pre表示上一次有订单的时间
c表示优先级
f表示是否在优先缓存中(true表示在优先缓存中,false表示不在)
*/
for(auto d:dd[id]){
//cout<<d<<" ";
if(d!=pre) c-=d-pre-1;//处理没有订单的时间段,c减去订单数为0的时间段
if(c<=3) f=false;//优先级小于等于3,因此不在优先级中
if(c<0) c=0;//优先级最低减到0
c+=2;//id店铺在d时刻有订单,所以c+2
if(c>5) f=true;
pre=d;
}
c-=t-pre;//特别处理pre-t时间段,若之间没有订单则需要减去
if(c<=3) f=false;
if(f) ans++;
}
cout<<ans;
return 0;
}