牛啊牛啊
正解是统计出 同一时刻,同一商家的订单,时间的间隔来削减优先级
外层循环是 每个订单,内层循环是 相同时间相同商家的这些订单进行批处理
用last数组来存储上一次有订单的时间
#include<bits/stdc++.h>
using namespace std;
struct Node{
int time,id;
bool operator<(const Node& nd)const
{
if(time!=nd.time) return time<nd.time;
return id<nd.id;
}
bool operator==(const Node& nd)const
{
if(time==nd.time && id==nd.id) return true;
return false;
}
};
const int N = 100010;
int n,m,T;
int prior[N]; //优先级
int last[N]; //上一次出现的时间
int st[N]; //是否在缓冲队列中
Node orders[N];
int main()
{
cin>>n>>m>>T;
for(int i=0;i<m;i++)
{
int t,id;
scanf("%d%d",&t,&id);
orders[i]={t,id};
}
sort(orders,orders+m);
for(int i=0;i<m;)
{
int j=i;
while(orders[j]==orders[i] && j<m) j++;
int time=orders[i].time,id=orders[i].id;
//记录的是这次订单发生的时间
int cnt=j-i; //这次批处理的订单个数
i=j;
//将这次订单之前的削减时间完成了
prior[id]-=time-last[id]-1; //因为订单有加则不削减
if(prior[id]<0) prior[id]=0;
if(prior[id]<=3) st[id]=0;
prior[id]+=cnt*2;
if(prior[id]>5) st[id]=1;
last[id]=time;
}
//每家店的最后一段是没有计算削减的,要补充上
for(int i=1;i<=n;i++)
{
if(last[i]<T)
{
prior[i]-=T-last[i];
}
if(prior[i]<=3) st[i]=0;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(st[i]>0) ans++;
}
cout<<ans;
return 0;
}